Copil Copac 画树

• 时间限制：3 秒
• 内存限制：256 MiB

题目描述

Copil Copac 得到了一棵有 $n$ 个顶点的树的 $n-1$ 条边的列表。他决定用如下算法绘制这棵树：

• 第 $0$ 步：画出第一个顶点（顶点 $1$）。进入第 $1$ 步。
• 第 $1$ 步：对于输入中的每一条边，按顺序：如果这条边连接了一个已经画出的顶点 $u$ 和一个未画出的顶点 $v$，他就画出未画出的顶点 $v$ 以及这条边。检查完所有边后，进入第 $2$ 步。
• 第 $2$ 步：如果所有顶点都已画出，算法终止。否则，回到第 $1$ 步。

“读边次数”定义为 Copil Copac 执行第 $1$ 步的次数。

请你求出 Copil Copac 绘制这棵树所需的读边次数。

输入格式

每个测试点包含多个测试用例。输入的第一行包含一个整数 $t$（$1 \leq t \leq 10^4$），表示测试用例的数量。接下来是每个测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$2 \le n \le 2 \cdot 10^5$），表示树的顶点数。

接下来的 $n-1$ 行，每行包含两个整数 $u_i$ 和 $v_i$（$1 \le u_i, v_i \le n$，$u_i \neq v_i$），表示第 $i$ 条边连接 $u_i$ 和 $v_i$。保证给出的边集构成一棵树。

保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

输出格式

对于每个测试用例，输出 Copil Copac 绘制这棵树所需的读边次数。

样例输入 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\le t\le10^4$，$2\le n\le2\times10^5$；每组给出的 $n-1$ 条边构成一棵树，所有测试用例中 $n$ 的总和不超过 $2\times10^5$。