33312번 - Remove Exactly Two 다국어

문제

Recently, Little John got a tree from his aunt to decorate his house. But as it seems, just one tree is not enough to decorate the entire house. Little John has an idea. Maybe he can remove a few vertices from the tree. That will turn it into more trees! Right?

You are given a tree¹ of $n$ vertices. You must perform the following operation exactly twice.

• Select a vertex $v$;
• Remove all edges incident to $v,ドル and also the vertex $v$.

Please find the maximum number of connected components after performing the operation exactly twice.

Two vertices $x$ and $y$ are in the same connected component if and only if there exists a path from $x$ to $y$. For clarity, note that the graph with 0ドル$ vertices has 0ドル$ connected components by definition.²

¹A tree is a connected graph without cycles.

²But is such a graph connected?

입력

Each test contains multiple test cases. The first line contains the number of test cases $t$ (1ドル \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ (2ドル \le n \le 2 \cdot 10^5$).

Each of the next $n-1$ lines contains two integers $u_i$ and $v_i,ドル denoting the two vertices connected by an edge (1ドル \le u_i,v_i \le n,ドル $u_i \neq v_i$). It is guaranteed that the given edges form a tree.

It is guaranteed that the sum of $n$ over all test cases does not exceed 2ドル \cdot 10^5$.

출력

For each test case, output the maximum number of connected components on a separate line.

제한

노트

On the first test case, removing a vertex twice will make the graph empty. By definition, the number of connected components in the graph with 0ドル$ vertices is 0ドル$. Therefore, the answer is 0ドル$.

On the second test case, removing two vertices 1ドル$ and 2ドル$ leaves 2ドル$ connected components. As it is impossible to make 3ドル$ connected components with 2ドル$ vertices, the answer is 2ドル$.

On the third test case, removing two vertices 1ドル$ and 5ドル$ leaves 4ドル$ connected components, which are $\left\{ 2,4\right\},ドル $\left\{ 3\right\},ドル $\left\{ 6\right\},ドル and $\left\{ 7\right\}$. It can be shown that it is impossible to make 5ドル$ connected components. Therefore, the answer is 4ドル$.