Tree Centroid

You are given one or more test cases. In each test case, an undirected tree is described by its number of nodes and the list of its edges. A tree is an acyclic connected graph. The centroid of a tree is a node such that when removed, the size of the largest remaining connected component is minimized. Equivalently, a node ( x ) is a centroid if for every connected subtree (after removal of ( x )) the number of nodes is not more than ( \frac{N}{2} ).

Your task is to determine the centroid of the tree for each test case.

Note: It is guaranteed that each test case has a unique centroid.

inputFormat

The input consists of multiple test cases. Each test case begins with a line containing a single integer ( N ) (the number of nodes). For a test case with ( N > 1 ), the next ( N-1 ) lines each contain two integers ( u ) and ( v ) denoting an edge between nodes ( u ) and ( v ). A test case with ( N = 1 ) has no additional lines. The input is terminated by a line containing the single character '0'.

outputFormat

For each test case, output a single line containing the centroid of the corresponding tree.## sample

1
0

1