acmsguru |
---|
Finished |
134. Centroid time limit per test: 0.25 sec.
You are given an undirected connected graph, with N vertices and N-1 edges (a tree). You must find the centroid(s) of the tree.
Input The first line of the input contains the integer number N (1<=N<=16 000). The next N-1 lines will contain two integers, a and b, separated by blanks, meaning that there exists an edge between vertex a and vertex b.
Output You should print two lines. The first line should contain the minimum value associated to the centroid(s) and the number of centroids. The second line should contain the list of vertices which are centroids, sorted in ascending order.
Sample Input 7 1 2 2 3 2 4 1 5 5 6 6 7
Sample Output 3 1 1 | ||||||
|
Name |
---|