ZOJ Problem Set - 4087
Little Sub has an unrooted tree with $n$ vertices. He would like to choose $k$ special vertices $s_1,s_2,\dots,s_k$ and encode each vertex $u$ as an array of $k$ elements in the following way: the $i$-th element equals to the number of vertices in the shortest path from $s_i$ to $u$.
Each vertex should have a unique encoding. Little Sub would like to find the minimum $k$.
There are multiple test cases. The first line of input contains an integer $T$ indicating the number of test cases. For each test case:
The first line contains an integer $n$ ($2 \le n \le 10^5$) -- the number of vertices in the tree. Each of the next $n-1$ lines contains two integers $u_i$ and $v_i$ $(1 \le u_i, v_i \le n, u_i \ne v_i)$ -- an edge in the tree.
It is guaranteed that the sum of all $n$ does not exceed $10^6$.
For each test case, output an integer $k$ in the first line denoting the minimum number of special vertices. Then in the second line, output $k$ integers $s_1,s_2,\dots,s_k$ denoting a possible solution.
1 4 4 1 4 2 4 3
2 2 3
Author: GUO, Wenrui
Source: ZOJ Monthly, January 2019