题目描述

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$），代表 $u$ 和 $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
0
4

说明

在第一个测试样例中，原树直径为 $3$。Kagari 可以选取 $s=3,t=4$ 执行一次操作，操作过程如下：

1. 删除边 $(3,1),(1,2),(2,4)$；
2. 添加边 $(3,1),(3,2),(3,4)$。

操作之后，树的直径变为 $2$，并且可以证明 $2$ 是该树能达到的最小直径。

第二个测试样例中，树的直径已经是 $1$，这就是它能达到的最小值，不需要执行任何操作。

原题链接

原题链接