CF1689C.Infected Tree

Byteland is a beautiful land known because of its beautiful trees.

Misha has found a binary tree with $n$ vertices, numbered from $1$ to $n$. A binary tree is an acyclic connected bidirectional graph containing $n$ vertices and $n - 1$ edges. Each vertex has a degree at most $3$, whereas the root is the vertex with the number $1$ and it has a degree at most $2$.

Unfortunately, the root got infected.

The following process happens $n$ times:

• Misha either chooses a non-infected (and not deleted) vertex and deletes it with all edges which have an end in this vertex or just does nothing.
• Then, the infection spreads to each vertex that is connected by an edge to an already infected vertex (all already infected vertices remain infected).

As Misha does not have much time to think, please tell him what is the maximum number of vertices he can save from the infection (note that deleted vertices are not counted as saved).

Byteland 是一片以美丽树木而闻名的土地。

米沙发现了一棵包含 $n$ 个顶点的二叉树，顶点编号从 $1$ 到 $n$。二叉树是一种无环、连通、无向图，包含 $n$ 个顶点和 $n - 1$ 条边；每个顶点的度数至多为 $3$，而根节点是编号为 $1$ 的顶点，其度数至多为 $2$。

不幸的是，根节点被感染了。

接下来的过程将执行 $n$ 轮：

• 米沙要么选择一个未被感染且未被删除的顶点，并将其（以及所有以该顶点为端点的边）删除；要么什么都不做。
• 然后，感染会沿着边传播：所有与已感染顶点相邻的顶点均被感染（所有已感染顶点保持感染状态）。

由于米沙没有太多时间思考，请你告诉他：他最多能拯救多少个顶点免于感染？（注意：被删除的顶点不计入被拯救的顶点。）

There are several test cases in the input data. The first line contains a single integer $t$ ($1\leq t\leq 5000$) — the number of test cases. This is followed by the test cases description.

The first line of each test case contains one integer $n$ ($2\leq n\leq 3\cdot 10^5$) — the number of vertices of the tree.

The $i$-th of the following $n-1$ lines in the test case contains two positive integers $u_i$ and $v_i$ ($1 \leq u_i, v_i \leq n$), meaning that there exists an edge between them in the graph.

It is guaranteed that the graph is a binary tree rooted at $1$. It is also guaranteed that the sum of $n$ over all test cases won't exceed $3\cdot 10^5$.

输入数据包含多个测试用例。第一行包含一个整数 $t$（$1\leq t\leq 5000$），表示测试用例的数量。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$2\leq n\leq 3\cdot 10^5$），表示树的顶点数。

接下来的 $n-1$ 行中，第 $i$ 行包含两个正整数 $u_i$ 和 $v_i$（$1 \leq u_i, v_i \leq n$），表示图中存在一条连接它们的边。

保证该图是一棵以顶点 $1$ 为根的二叉树。同时保证所有测试用例的 $n$ 值之和不超过 $3\cdot 10^5$。

For each test case, output the maximum number of vertices Misha can save.

对于每个测试用例，输出米沙最多能拯救的顶点数量。

In the first test case, the only possible action is to delete vertex $2$, after which we save $0$ vertices in total.

In the second test case, if we delete vertex $2$, we can save vertices $3$ and $4$.

在第一个测试用例中，唯一可能的操作是删除顶点 $2$，之后总共保留下 $0$ 个顶点。

在第二个测试用例中，如果我们删除顶点 $2$，则可以保留下顶点 $3$ 和 $4$。