Centroid Selection in a Tree

John's network is structured as a tree with N barns. Bessie, angry after being fired, wishes to maximize her revenge by cutting the power of one barn. Cutting the power at barn v causes all cables incident to v to disconnect, splitting the tree into several sub-networks. In order for the damage to be significant, each resulting sub-network must contain no more than \(\frac{N}{2}\) barns. Your task is to find all barns for which, if the power is cut, every connected component (subtree) has at most \(\frac{N}{2}\) nodes.

Note:

• The tree is given as an undirected graph with N nodes and N-1 edges, and nodes are numbered from 1 to N.
• If a node is removed (i.e. its power is cut), consider each connected component that forms. For the removal of node v, let \(S_u\) be the size of the subtree rooted at a neighbor u (when v is removed) and let \(R = N - size(v)\) be the size of the remainder of the tree (the component not in the subtree of v). The node v is eligible if each \(S_u\) and \(R\) (if applicable) is \(\leq \frac{N}{2}\).

inputFormat

The first line contains an integer N (the number of barns).
Each of the next N-1 lines contains two integers u and v denoting an edge between barns u and v.

outputFormat

Output all barn numbers that, when removed, result in all connected components having at most \(\frac{N}{2}\) nodes. The numbers should be printed in increasing order, separated by spaces.

sample

6
1 2
1 3
2 4
2 5
3 6

1 2