Welcome to ZOJ
Select Problem
ZOJ Problem Set - 4087
Little Sub and Tree

Time Limit: 2 Seconds      Memory Limit: 65536 KB      Special Judge

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.

Sample Input

4 1
4 2
4 3

Sample Output

2 3

Author: GUO, Wenrui
Source: ZOJ Monthly, January 2019
Submit    Status