CF2131D Arboris Contractio

Kagari 正准备对一棵树进行归档，她知道归档的成本取决于树的直径 ¹。为了降低成本，她的目标是首先尽可能缩小直径。她可以对树执行以下操作： - 选择两个顶点 $s$ 和 $t$。设从 $s$ 到 $t$ 的简单路径 ² 上的顶点序列为 $v_{0},v_{1},…,v_{k}$，其中 $v_{0} = s,v_{k} = t$。 移除路径上的所有边。即移除边 $(v_{0},v_{1}),(v_{1},v_{2}),…,(v_{k-1},v_{k})$。 - 将顶点 $v_{1},v_{2},…,v_{k}$ 直接连接到 $v_{0}$。即添加边 $(v_{0},v_{1}),(v_{0},v_{2}),…,(v_{0},v_{k})$。 可以证明，操作后图仍然是一棵树。 请帮助她确定实现最小直径所需的最少操作次数。 ___ 注释： ¹ 树的直径是任意两个顶点之间可能的最长距离。距离本身通过连接它们的唯一简单路径上的边数来衡量。 ² 简单路径是树中两个顶点之间的路径，且不会重复访问任何顶点。可以证明，任意两个顶点之间的简单路径总是唯一的。

每个测试包含多个测试用例。 第一行包含测试用例的数量 $t(1≤t≤10^4)$。 每个测试用例的第一行包含一个整数 $n(2≤n≤2⋅10^5)$，表示树中顶点的数量。 每个测试用例的接下来 $n−1$ 行描述树。每行包含两个整数 $u$ 和 $v(1≤u,v≤n,u≠v)$，表示顶点 $u$ 和 $v$ 之间有一条边。保证这些边构成一棵树。 保证所有测试用例的 $n$ 之和不超过 $2⋅10^5$。

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

在第一个测试用例中，原始树的直径为 $3$。Kagari 可以对 $s=3$ 和 $t=4$ 执行操作。操作包括以下步骤： - 移除边 $(3,1)$, $(1,2)$ 和 $(2,4)$。 - 添加边 $(3,1)$, $(3,2)$ 和 $(3,4)$。 操作后，直径减小到 $2$。可以证明 $2$ 是最小直径。 在第二个测试用例中，树的直径为 $1$。 可以证明 $1$ 已经是最小值，因此 Kagari 无需执行操作。