Rabbit

赫尔德不知道这样是否好，为了研究这个活动，她想先从这个活动能持续多久开始研究。于是她抽象了这个问题。 给定一棵树，共 $n$ 个点，分别编号为 $1\sim n$。 每次操作，你需要选出三个点 $a,b,c$ 将他们标记，满足： - $c$ 是 $a$ 到 $b$ 简单路径上编号最大的点； - $a,b,c$ 两两不同； - $a,b,c$ 先前都没有被标记过。 问至多能进行多少次操作。 --- **【提示】** 树上 $p$ 到 $q$ 的简单路径是指一个数列 $a_1,\dots,a_k$，满足： 1. $a_1=p$，$a_k=q$； 2. 其中没有重复元素； 3. 对于所有 $1\le i<k$，$a_{i+1}$ 与 $a_i$ 有边相连。 ## Input 本题有多组数据。 第一行是数据组数 $T$，接下来 $T$ 组数据，每组数据格式如下： 第一行一个正整数 $n$。 接下来 $n-1$ 行，每行两个正整数 $x,y$，描述树上的一条连接 $x,y$ 的边。 ## Output 对于每组数据输出一行一个非负整数，为答案。 [samples] ## Background “说实话，最喜欢你了；因为长得好看，所以最喜欢你了。 你的性格，我最喜欢了；虽然不太清楚，但是最喜欢了。” 赫尔德最近加入了一个奇怪的社区，那里面流行一种“配对追星”的活动。大家在人群中找到那个最耀眼的人，就作为自己的偶像了。 ## Note **【样例解释】** 对于第一组数据，可以选择 $a=1,b=2,c=3$。 对于第三组数据，可以依次选择 $a=3,b=4,c=7$，$a=1,b=2,c=5$。 --- **【数据范围】** 设 $S$ 为每个测试点所有数据中 $n$ 的和。 对于所有数据：$1\le T\le 3\times 10^4$，$1\le n\le 2\times 10^5$，$S\le 6\times 10^5$。 $$ \begin{array}{c|c|c|c|c|c} \hline \textbf{子任务编号} & ~~~~~~~n\le ~~~~~~~ & ~~~~~~~S\le ~~~~~~~ & \textbf{特殊性质} & \textbf{子任务依赖} & \textbf{~~~分数~~~} \\ \hline \textsf{1} & 5 & & & & 3 \\ \hline \textsf{2} & 20 & 60 & & & 5 \\ \hline \textsf{3} & & & \textsf{B} & & 12 \\ \hline \textsf{4} & 333 & 10^3 & \textsf{A} & & 9 \\ \hline \textsf{5} & 333 & 10^3 & & \textsf{2,4} & 7 \\ \hline \textsf{6} & 3333 & 10^4 & \textsf{A} & \textsf{4} & 15 \\ \hline \textsf{7} & 3333 & 10^4 & & \textsf{5,6} & 13 \\ \hline \textsf{8} & & & \textsf{A} & \textsf{6} & 12 \\ \hline \textsf{9} & & & & \textsf{1,3,7,8} & 24 \\ \hline \end{array} $$ 特殊限制 $\textsf{A}$：保证树的形态是一条链，即树上不存在度数大于 2 的点。 特殊限制 $\textsf{B}$：保证树随机生成：对于每个整数 $i\in [2,n]$，均匀随机选择整数 $j\in [1,i-1]$ 并在 $i,j$ 间连边，然后随机打乱点的编号。