树的绘制 (tree)

• 输入：tree.in
• 输出：tree.out
• 时间限制：1 s
• 内存限制：256 MB

题目描述

小 A 正在学习如何用程序画一棵树。

给定一棵有 $n$ 个点的树，点的编号为 $1$ 到 $n$。这棵树的 $n-1$ 条边按输入顺序编号为 $1$ 到 $n-1$。

一开始，小 A 只画出了点 $1$。之后他会不断重复下面的过程：

• 从第 $1$ 条边到第 $n-1$ 条边，按输入顺序依次检查每条边。
• 如果当前边连接了一个已经画出的点和一个还没有画出的点，那么他会立刻画出这个还没有画出的点，以及这条边。
• 如果当前边的两个端点都已经画出，或者都还没有画出，则什么也不做。

每完整检查一遍所有边，称为一次“读边”。

当所有点都被画出后，绘制结束。请你求出小 A 至少需要读边多少次。

输入格式

从文件 tree.in 中读入数据。

第一行包含一个整数 $t$，表示测试数据组数。

对于每组数据：

第一行包含一个整数 $n$。

接下来 $n-1$ 行，每行包含两个整数 $u_i,v_i$，表示第 $i$ 条边连接点 $u_i$ 和点 $v_i$。

保证每组数据给出的边构成一棵树。

输出格式

输出到文件 tree.out 中。

对于每组数据，输出一行一个整数，表示绘制这棵树需要的读边次数。

样例1输入

2
6
4 5
1 3
1 2
3 4
1 6
7
5 6
2 4
2 7
1 3
1 2
4 5

样例1输出

2
3

样例1解释

对于第一组数据，第一次读边时可以画出点 $3,2,6$，并且在继续向后读到边 $(3,4)$ 时，还可以画出点 $4$。

但边 $(4,5)$ 出现在输入的最前面，在第一次读边时点 $4$ 还没有被画出，所以点 $5$ 不能在第一次读边时画出。

第二次读边时，边 $(4,5)$ 可以生效，于是点 $5$ 被画出。因此答案为 $2$。

数据范围

对于所有数据，$1 \le t \le 10000$，$2 \le n \le 200000$，保证所有测试数据中 $n$ 的总和不超过 $200000$。每个测试点 $5$ 分。