Problem Description

Since the last time the Divine Blade helped the Earthworm Kingdom increase by tens of millions of people (earthworm population?), the Earthworm Kingdom has been developing more and more prosperously! Recently, they discovered some magical papers underground, and after careful study, they turned out to be the design blueprints of a supercomputer in City X, Country D!

This computer is called the "Tree Diagram," consisting of $n$ computational nodes connected by $n - 1$ bidirectional communication lines, with all computational nodes numbered by positive integers not exceeding $n$. As the name suggests, this forms a tree structure.

The Earthworm King has mastered the complete information of this tree, including the value of $n$ and the connection information of the $n - 1$ lines. Therefore, the Earthworm King decided to dispatch the two most powerful hackers in the Earthworm Kingdom, Xiao P and Xiao H, to infiltrate the "Tree Diagram" and destroy it as much as possible.

Xiao P and Xiao H are proficient in the best programming languages in the world. After some discussion, they decided to take the following steps sequentially:
- Xiao P selects a computational node as his starting point and marks it with a P.
- Repeat the following operation several times (can be $0$ times):
- Xiao P starts from his current computational node, selects an unmarked line, infiltrates to the computational node at the other end of the line, and marks both the line and the destination node with a P.
- Xiao H selects a computational node as her starting point and marks it with an H.
- Repeat the following operation several times (can be $0$ times):
- Xiao H starts from her current computational node, selects an unmarked line, infiltrates to the computational node at the other end of the line, and marks both the line and the destination node with an H. (Note that Xiao H cannot pass through lines marked with P, but can pass through nodes marked with P)
- Delete all marked computational nodes and lines.
- For each remaining line, if one or both of its endpoints were deleted in the previous step, delete this line as well.

After the above operations, the "Tree Diagram" will be disconnected, leaving several (possibly $0$) connected components. To achieve the purpose of destruction, the Earthworm King hopes that the number of connected components will be as large as possible. Therefore, he has come to you, hoping you can help him calculate this maximum number.

Xiao P and Xiao H are very impatient. Before you calculate the plan, they may have already figured out the optimal plan or part of it. You will be given a value $x$:
- If $x = 0$, it means Xiao P and Xiao H have not figured out the optimal plan, and you need to determine their infiltration routes.
- If $x = 1$, it means Xiao P has figured out his part of the optimal plan in a cooperative scenario. He will select the starting point $p_0$ and infiltrate along the lines to the target point $p_1$, and he will not infiltrate further along the lines; you only need to determine Xiao H's infiltration route.
- If $x = 2$, it means Xiao P and Xiao H have figured out a cooperative optimal plan, where Xiao P infiltrates from point $p_0$ to $p_1$ and stops, and Xiao H infiltrates from point $h_0$ to $h_1$ and stops. At this point, you do not need to direct their infiltration; you only need to calculate the number of remaining connected components after the last two steps of deleting nodes and lines.

Input Format

Each input file contains multiple input data. The first line of the input file is two integers $T$ and $x$, where $T$ represents the number of input data in the file, and the meaning of $x$ is as described above. (All data in the same input file have the same $x$.)

The input data follows sequentially.

Output Format

For each data, output one line, representing the maximum number of remaining connected components under the given conditions.

Sample Input and Output

Input Sample #1

1 0
13
1 2
2 3
2 4
4 5
4 6
4 7
7 8
7 9
9 10
10 11
10 12
12 13

Output Sample #1

8

Input Sample #2

8 0
1
2
1 2
3
1 2
2 3
4
1 3
2 3
2 4
5
1 5
2 5
3 5
4 5
16
1 2
1 3
1 4
1 5
5 6
5 7
5 8
5 9
9 10
9 11
9 12
9 13
13 14
13 15
13 16
17
1 2
1 3
1 4
1 5
5 6
5 7
5 8
5 17
17 9
9 10
9 11
9 12
9 13
13 14
13 15
13 16
17
8 6
2 6
11 6
4 6
14 2
10 2
5 4
1 4
9 8
17 11
12 5
3 6
13 6
16 8
7 11
15 16

Output Sample #2

0
1
2
2
4
12
13
10

Input Sample #3

8 1
1 1 1
2 1 1
1 2
3 2 2
1 2
2 3
4 2 2
1 3
2 3
2 4
5 5 5
1 5
2 5
3 5
4 5
16 1 5
1 2
1 3
1 4
1 5
5 6
5 7
5 8
5 9
9 10
9 11
9 12
9 13
13 14
13 15
13 16
17 1 5
1 2
1 3
1 4
1 5
5 6
5 7
5 8
5 17
17 9
9 10
9 11
9 12
9 13
13 14
13 15
13 16
17 2 4
8 6
2 6
11 6
4 6
14 2
10 2
5 4
1 4
9 8
17 11
12 5
3 6
13 6
16 8
7 11
15 16

Output Sample #3

0
1
2
2
4
12
13
10

Notes/Hints

• If $x = 0$, this line contains only one integer $n$.
• If $x = 1$, this line contains three integers $n, p_0, p_1$.
• If $x = 2$, this line contains five integers $n, p_0, p_1, h_0, h_1$.

Ensure that $p_0, p_1, h_0, h_1$ are positive integers not exceeding $n$.

Each data follows with $n - 1$ lines, each containing two positive integers not exceeding $n$, indicating that there is a line connecting these two numbered computational nodes. The input guarantees a tree structure.

Integers in the same line are separated by exactly one space.

The data file may be large, so avoid using slow input/output methods.

Sample 1 Explanation:

This input file contains only one data. An optimal solution is as follows:
- Xiao P starts infiltration from node $2$, which is marked by Xiao P.
- Xiao P infiltrates from node $2$ to node $4$, marking node $4$ and the line.
- Xiao P infiltrates from node $4$ to node $7$, marking node $7$ and the line.
- Xiao H starts infiltration from node $10$, which is marked by Xiao H.
- Delete the marked nodes $2, 4, 7, 10$ and the marked lines $(2, 4)$ and $(4, 7)$.
- Delete any line whose one or both endpoints were deleted in the previous step.

At this point, there are $8$ connected components left. Nodes $1, 3, 5, 6, 8, 9, 11$ each form a connected component, and nodes $12, 13$ form another connected component.

Sample 2 Explanation:

• Data 1: There is only $1$ computational node, and the only feasible solution is Xiao P starting from node $1$ (and immediately stopping), and Xiao H also starting from node $1$ to node $1$. All nodes are deleted, leaving $0$ connected components.
• Data 2: An optimal solution is Xiao P starting from node $1$ to node $1$, and Xiao H also starting from node $1$ to node $1$. After the deletion, $1$ connected component remains (only node $2$).
• Data 3: The only optimal solution is Xiao P starting from node $2$ to node $2$, and Xiao H also starting from node $2$ to node $2$, leaving $2$ connected components.
• Data 4: An optimal solution is Xiao P starting from node $2$ to node $2$, and Xiao H also starting from node $2$ to node $2$, leaving $2$ connected components.
• Data 5: The only optimal solution is Xiao P starting from node $5$ to node $5$, and Xiao H also starting from node $5$ to node $5$, leaving $4$ connected components.

Data Range:

For integer $k$, let $\sum n^k$ be the sum of $n^k$ for the $T$ input data in a file.

For all data, $T \leq 10^5, \sum n^1 < 5 \times 10^5$.

Please be aware of the time complexity of initialization to avoid timeout when inputting a large number of small data.

Detailed data ranges for each test point are provided in the table below. If "Complete Binary" is Yes, then each data in the input file satisfies: the $j$-th line $(1 \leq j < n)$ inputs two numbers, which are $\left\lfloor \frac{j + 1}{2} \right\rfloor$ and $j + 1$.

见题面 Input 部分

见题面 Output 部分