Kagari 正准备归档一棵树,她知道这样做的成本将取决于它的直径$$$^{\text{*}}$$$。为了降低成本,她的目标是首先尽可能缩小直径。她可以对树执行以下操作:
- 选择两个顶点 $$$s$$$ 和 $$$t$$$。设简单路径$$$^{\text{†}}$$$ 上从$$$s$$$ 到$$$t$$$ 的顶点序列为$$$v_0, v_1, \dots, v_k$$$,其中$$$v_0 = s$$$ 且$$$v_k = t$$$。
- 删除路径上的所有边。换句话说,删除边 $$$(v_0, v_1), (v_1, v_2), \dots, (v_{k-1}, v_k)$$$。
- 将顶点 $$$v_1, v_2, \dots, v_k$$$ 直接连接到 $$$v_0$$$。换句话说,添加边 $$$(v_0, v_1), (v_0, v_2), \dots, (v_0, v_k)$$$。
可以看出,运算后的图仍然是一棵树。
帮助她确定实现最小直径所需的最少操作次数。
$$$^{\text{*}}$$$树的直径是任意一对顶点之间的最长可能距离。距离本身是通过连接它们的唯一简单路径上的边数来测量的。
$$$^{\text{†}}$$$简单路径是树中两个顶点之间的路径,不会多次访问任何顶点。可以证明,任意两个顶点之间的简单路径总是唯一的。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$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$$$),表示顶点 $$$u$$$ 和 $$$v$$$ 之间的边。保证这些边形成一棵树。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出一个整数——最小化直径的最小操作数。
示例
输入复制
441 21 32 422 141 22 32 4111 21 32 43 53 85 65 77 97 105 11
输出复制
1 0 0 4
注意
在第一个测试用例中,原始树的直径为$$$3$$$。 Kagari 可以对 $$$s = 3$$$ 和 $$$t = 4$$$ 执行操作。如图所示,操作包括以下步骤:
- 删除边 $$$(3, 1)$$$、$$$(1, 2)$$$ 和 $$$(2, 4)$$$。
- 添加边 $$$(3, 1)$$$、$$$(3, 2)$$$ 和 $$$(3, 4)$$$。
手术后,直径减小到$$$2$$$。可以看出$$$2$$$是最小直径。
在第二个测试用例中,树的直径为$$$1$$$。可以看出$$$1$$$已经是最小值,所以Kagari不能执行任何操作。