Given a tree with nodes, find all centroid nodes in increasing order.
A centroid node is a node that, when removed, splits the tree into subtrees such that each subtree has nodes.
Constraints
Input Specification
The first line of input will contain .
The next lines will contain integers and denoting an edge between the two nodes.
Output Specification
On the first line, output the number of centroid nodes, .
On the next lines, output the centroid nodes in increasing order.
Sample Input 1
4
1 2
3 2
4 3
Sample Output 1
2
2
3
The two centroids are nodes and .
Sample Input 2
10
1 2
2 3
3 5
3 6
3 7
2 4
2 8
8 9
9 10
Sample Output 2
1
2
Explanation for Sample Output 2
The only node that is a centroid is node .
Comments