
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$. InputThere 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 $n1$ 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$. OutputFor 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. Sample Input1 4 4 1 4 2 4 3 Sample Output2 2 3 Author: GUO, Wenrui Source: ZOJ Monthly, January 2019 