当前没有测试数据。

D. Arboris Contractio

题目描述

Kagari 准备归档一棵树木，她知道归档的成本取决于树的直径∗。为了降低开销，她的目标是先尽可能缩小树的直径。她可以对树执行以下操作：

1. 选择两个顶点 $s$ 和 $t$。设从 $s$ 到 $t$ 的简单路径†上的顶点序列为 $v_0, v_1, \dots, v_k$，其中 $v_0 = s$ 且 $v_k = t$。
2. 移除路径上的所有边。即移除边 $(v_0, v_1), (v_1, v_2), \dots, (v_{k-1}, v_k)$。
3. 将顶点 $v_1, v_2, \dots, v_k$ 直接连接到 $v_0$。即添加边 $(v_0, v_1), (v_0, v_2), \dots, (v_0, v_k)$。

可以证明，操作后得到的图仍然是一棵树。

请帮助她确定需要的最少操作次数，以实现最小可能的直径。

∗ 树的直径是指任意两个顶点之间的最长距离，距离定义为连接这两个顶点的唯一简单路径上的边数。 † 简单路径是指树中两个顶点之间不重复访问任何顶点的路径。可以证明，任意两个顶点之间的简单路径是唯一的。

输入格式

输入包含多组测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。

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

接下来的 $n-1$ 行，每行包含两个整数 $u$ 和 $v$（$1 \le u, v \le n$，$u \neq v$），表示树中的一条边。保证输入的边构成一棵合法的树。

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

输出格式

对于每组测试用例，输出一个整数，表示实现最小直径所需的最少操作次数。

样例输入

4
4
1 2
1 3
2 4
2
2 1
4
1 2
2 3
2 4
11
1 2
1 3
2 4
3 5
3 8
5 6
5 7
7 9
7 10
5 11

样例输出

1
0
1
4

提示

在第一个测试用例中，原树的直径为 3。Kagari 可以选择 $s = 3$ 和 $t = 4$ 执行一次操作，步骤如下：

1. 移除边 $(3, 1)$、$(1, 2)$ 和 $(2, 4)$。
2. 添加边 $(3, 1)$、$(3, 2)$ 和 $(3, 4)$。

操作后，树的直径缩小到 2，这是最小可能的直径。

在第二个测试用例中，原树的直径为 1，已经是最小可能值，因此无需执行任何操作。

（提示中的图片链接：https://espresso.codeforces.com/467bf647ed9e08a9d0b5a5ae0054b9dd76da0a9e.png）