CF1695D1.Tree Queries (Easy Version)

The only difference between this problem and D2 is the bound on the size of the tree.

You are given an unrooted tree with $n$ vertices. There is some hidden vertex $x$ in that tree that you are trying to find.

To do this, you may ask $k$ queries $v_1, v_2, \ldots, v_k$ where the $v_i$ are vertices in the tree. After you are finished asking all of the queries, you are given $k$ numbers $d_1, d_2, \ldots, d_k$, where $d_i$ is the number of edges on the shortest path between $v_i$ and $x$. Note that you know which distance corresponds to which query.

What is the minimum $k$ such that there exists some queries $v_1, v_2, \ldots, v_k$ that let you always uniquely identify $x$ (no matter what $x$ is).

Note that you don't actually need to output these queries.

本题与 D2 的唯一区别在于树的大小限制。

你被给定一棵包含 $n$ 个顶点的无根树。该树中存在某个隐藏顶点 $x$，你需要找出它。

为此，你可以提出 $k$ 次查询 $v_1, v_2, \ldots, v_k$，其中每个 $v_i$ 均为树中的一个顶点。在你完成全部查询后，你将获得 $k$ 个数 $d_1, d_2, \ldots, d_k$，其中 $d_i$ 表示 $v_i$ 与 $x$ 之间最短路径上的边数。注意，你知道每个距离 $d_i$ 对应的是哪一个查询 $v_i$。

求最小的 $k$，使得存在一组查询 $v_1, v_2, \ldots, v_k$，能让你无论 $x$ 是哪一个顶点，总能唯一确定 $x$。

注意：你无需实际输出这些查询。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 100$). Description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 2000$) — the number of vertices in the tree.

Each of the next $n-1$ lines contains two integers $x$ and $y$ ($1 \le x, y \le n$), meaning there is an edges between vertices $x$ and $y$ in the tree.

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 $2000$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 100$）。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2000$）—— 表示树中顶点的数量。

接下来的 $n-1$ 行中，每行包含两个整数 $x$ 和 $y$（$1 \le x, y \le n$），表示树中顶点 $x$ 与顶点 $y$ 之间存在一条边。

保证所给的边构成一棵树。

保证所有测试用例的 $n$ 值之和不超过 $2000$。

For each test case print a single nonnegative integer, the minimum number of queries you need, on its own line.

对于每个测试用例，在单独一行中输出一个非负整数，即所需的最少查询次数。

In the first test case, there is only one vertex, so you don't need any queries.

In the second test case, you can ask a single query about the node $1$. Then, if $x = 1$, you will get $0$, otherwise you will get $1$.

在第一个测试用例中，只有一个顶点，因此你不需要进行任何查询。

在第二个测试用例中，你可以对节点 $1$ 进行一次查询。此时，若 $x = 1$，你将得到 $0$；否则，你将得到 $1$。