Background

"To be honest, I like you the most; because you look good, I like you the most.

Your personality, I like it the most; although I do not really understand it, I still like it the most."

Helde has recently joined a strange community where an activity called "paired idol-chasing" is popular. Everyone looks for the most eye-catching person in the crowd and treats them as their idol.

Problem Description

Helde is not sure whether this is a good thing. To study how this activity works, she wants to start by studying how long it can last, so she abstracted it into the following problem.

Given a tree with $n$ nodes, numbered $1 \sim n$.

In each operation, you need to choose three nodes $a, b, c$ and mark them, such that:

• $c$ is the node with the largest label on the simple path from $a$ to $b$;
• $a$, $b$, and $c$ are pairwise distinct;
• $a$, $b$, and $c$ have not been marked before.

Ask for the maximum number of operations that can be performed.

---

Hint

A simple path from $p$ to $q$ in a tree refers to a sequence $a_1, \dots, a_k$ that satisfies:

1. $a_1 = p$, $a_k = q$;
2. there are no repeated elements;
3. for all $1 \le i < k$, $a_{i+1}$ is connected to $a_i$ by an edge.

Input Format

This problem contains multiple test cases.

The first line contains the number of test cases $T$. Then follow $T$ test cases, each in the following format:

The first line contains a positive integer $n$.

In the next $n - 1$ lines, each line contains two positive integers $x, y$, describing an edge connecting $x$ and $y$ in the tree.

Output Format

For each test case, output one line containing one non-negative integer, the answer.

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

Hint

Sample Explanation

For the first test case, you can choose $a = 1, b = 2, c = 3$.

For the third test case, you can choose in order $a = 3, b = 4, c = 7$, and $a = 1, b = 2, c = 5$.

---

Constraints

Let $S$ be the sum of $n$ over all test cases within a test point.

For all testdata: $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}$$

Special restriction $\textsf{A}$: the tree is guaranteed to be a chain, meaning there is no node in the tree with degree greater than $2$.

Special restriction $\textsf{B}$: the tree is guaranteed to be generated randomly: for each integer $i \in [2, n]$, uniformly randomly choose an integer $j \in [1, i - 1]$ and add an edge between $i$ and $j$, then randomly shuffle the node labels.

Translated by ChatGPT 5