Tree Queries (Easy Version)
Contest: Codeforces Round 801 (Div. 2) and EPIC Institute of Technology Round
Difficulty rating: 2200
Tags: brute force, constructive algorithms, dfs and similar, dp, greedy, trees

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.

Input format:
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$$$.

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

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
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$$$.

Example input:
3
1
2
1 2
10
2 4
2 1
5 7
3 10
8 6
6 1
1 3
4 7
9 6

Example output:
0
1
2

Editorial:
If $$$n=1$$$, then no queries are needed, because there is only one vertex. Otherwise, we need at least one query.
If we fix a node $$$u$$$, and force it to be a query, we can root the tree at $$$u$$$ and do a greedy DFS to compute the answer. Note that because we guarantee that the root is a query, when we are computing the answer for any node $$$v$$$ in this DFS, we can assume that either $$$v$$$ or some vertex not in the subtree of $$$v$$$ has already been queried.
We define $$$ans[v]$$$ to be the minimal number of queries to distinguish all vertices in the subtree of $$$v$$$, given that $$$v$$$ or some vertex not in the subtree of $$$v$$$ has been queried. Note that for each child $$$c$$$ of $$$v$$$, we need to be able to distinguish all vertices in the subtree of $$$c$$$, so we have $$$ans[v] \geq \sum_c ans[c]$$$. Additionally, there can be at most one child $$$c$$$ of $$$v$$$ with no queries in its subtree, otherwise all of these children will be indistinguishable by the queries. If there are $$$x > 1$$$ such children of $$$v$$$, we can query the first $$$x-1$$$ of them, which will be enough to differentiate all vertices in these $$$x$$$ subtrees. So, using this definition of $$$x$$$, our final formula is
$$$$$$ans[v] = \sum_c ans[c] + max(0, x - 1)$$$$$$
For each possible root, we do a DFS to recursively compute these answers. The answer is the minimum $$$ans[root] + 1$$$, where the $$$+1$$$ is to account for the fact that we are querying the root.
Complexity: O(n^2)