题目描述

江月诗 有一棵 $n$ 个节点的树，节点编号为 $1 \sim n$。

对任意满足 $1 \le i < j \le n$ 的节点对 $(i,j)$，都需要在 $i,j$ 之间系上至少 $1$ 条绳子。

每次操作可以选定一个节点 $k$作为根；对于任意 $u \neq v$，若在以 $k$ 为根的树中 $u$ 是 $v$ 的祖先，则在$u,v$ 之间系上 $1$ 条绳子。

求最少需要进行多少次操作，就能满足所有节点对之间都系有至少一条绳子。

输入格式

本题包含多组测试数据。

第一行一个整数 $t$，表示数据组数。

每组数据：第一行一个整数 $n$。接下来 $n-1$ 行，每行两个整数$u,v$，表示树上一条边。

对于全部数据：$1 \le t \le 2\times 10^4$，$1 \le n \le 10^5$，所有测试数据的 $\sum n \le 2\times 10^5$，输入保证构成一棵树。

输出格式

每组数据输出一行一个整数，表示最少操作次数。

2
3
1 2
2 3
5
1 4
3 1
1 5
4 2

1
2

说明/提示

【样例解释】

对于第一组数据，树形态如图

只需要选择 $k = 1$ 做一次操作，就可以在节点 $1, 2$ 之间、$1, 3$ 之间和 $2, 3$ 之间都系上至少 $1$ 条绳子。

对于第二组数据，树形态如图

可以选择 $k = 3$ 和 $k = 5$ 分别进行操作：

• 在 $k = 3$ 时，会在节点对 $(1, 2), (1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (3, 4), (3, 5)$ 之间分别系上一条绳子；

• 在 $k = 5$ 时，会在节点对 $(1, 2), (1, 3), (1, 4), (1, 5), (2, 4), (2, 5), (3, 5), (4, 5)$ 之间分别系上一条绳子。

可以证明不存在操作次数小于 $2$ 的方案，于是答案为 $2$。