题目背景

“说实话，最喜欢你了；因为长得好看，所以最喜欢你了。

你的性格，我最喜欢了；虽然不太清楚，但是最喜欢了。”

赫尔德最近加入了一个奇怪的社区，那里面流行一种“配对追星”的活动。大家在人群中找到那个最耀眼的人，就作为自己的偶像了。

题目描述

赫尔德不知道这样是否好，为了研究这个活动，她想先从这个活动能持续多久开始研究。于是她抽象了这个问题。

给定一棵树，共 $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$ 有边相连。

输入格式

本题有多组数据。

第一行是数据组数 $T$，接下来 $T$ 组数据，每组数据格式如下：

第一行一个正整数 $n$。

接下来 $n-1$ 行，每行两个正整数 $x,y$，描述树上的一条连接 $x,y$ 的边。

输出格式

对于每组数据输出一行一个非负整数，为答案。

3
3
2 3
1 3
4
2 3
3 4
4 1
7
2 5
5 1
2 6
2 3
7 4
3 7

1
1
2

提示

【样例解释】

对于第一组数据，可以选择 $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$。

$$\def{\arraystretch}{1.5} \begin{array}{c|c|c|c|c|c}\hline \textbf{子任务编号}&~~~~~~~n\le ~~~~~~~&~~~~~~~S\le ~~~~~~~&\textbf{特殊性质}&\textbf{子任务依赖}&\textbf{~~~分数~~~}\cr\hline \textsf1 & 5 &&&&3\cr\hline \textsf2 & 20&60&&&5\cr\hline \textsf3 & & &\textsf{B}&&12\cr \hline \textsf4 & 333& 10^3&\textsf{A}&&9\cr \hline \textsf5 & 333 & 10^3&&\textsf{2,4}&7\cr\hline \textsf6 & 3333 &10^4&\textsf{A}&\textsf{4}&15\cr\hline \textsf7 & 3333 &10^4&&\textsf{5,6}&13\cr\hline \textsf8 & &&\textsf{A}&\textsf{6}&12\cr\hline \textsf9 & &&&\textsf{1,3,7,8}&24\cr\hline \end{array} $$

特殊限制 $\textsf{A}$：保证树的形态是一条链，即树上不存在度数大于 2 的点。

特殊限制 $\textsf{B}$：保证树随机生成：对于每个整数 $i\in [2,n]$，均匀随机选择整数 $j\in [1,i-1]$ 并在 $i,j$ 间连边，然后随机打乱点的编号。