# [Solution] Tree Queries (Hard Version) solution codeforces

Tree Queries (Hard Version) solution codeforces – You are given an unrooted tree with 𝑛n vertices. There is some hidden vertex 𝑥x in that tree that you are trying to find.

## [Solution] Tree Queries (Hard Version) solution codeforces

To do this, you may ask 𝑘k queries 𝑣1,𝑣2,,𝑣𝑘v1,v2,…,vk where the 𝑣𝑖vi are vertices in the tree. After you are finished asking all of the queries, you are given 𝑘k numbers 𝑑1,𝑑2,,𝑑𝑘d1,d2,…,dk, where 𝑑𝑖di is the number of edges on the shortest path between 𝑣𝑖vi and 𝑥x. Note that you know which distance corresponds to which query.

What is the minimum 𝑘k such that there exists some queries 𝑣1,𝑣2,,𝑣𝑘v1,v2,…,vk that let you always uniquely identify 𝑥x (no matter what 𝑥x is).

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

## [Solution] Tree Queries (Hard Version) solution codeforces

Each test contains multiple test cases. The first line contains the number of test cases 𝑡t (1𝑡1041≤t≤104). Description of the test cases follows.

The first line of each test case contains a single integer 𝑛n (1𝑛21051≤n≤2⋅105)  — the number of vertices in the tree.

Each of the next 𝑛1n−1 lines contains two integers 𝑥x and 𝑦y (1𝑥,𝑦𝑛1≤x,y≤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 21052⋅105.

## [Solution] Tree Queries (Hard Version) solution codeforces

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

Example
input

Copy
3
1
2
1 2
10
2 4
2 1
5 7
3 10
8 6
6 1
1 3
4 7
9 6


## [Solution] Tree Queries (Hard Version) solution codeforces

output

Copy
0
1
2

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 11. Then, if 𝑥=1x=1, you will get 00, otherwise you will get 11.