Score : 900 points
Takahashi has decided to make a Christmas Tree for the Christmas party in AtCoder, Inc.
A Christmas Tree is a tree with N vertices numbered 1 through N and N-1 edges, whose i-th edge (1\leq i\leq N-1) connects Vertex a_i and b_i.
He would like to make one as follows:
Takahashi would like to find the lexicographically smallest pair (A,B) such that he can make a Christmas Tree, that is, find the smallest A, and find the smallest B under the condition that A is minimized.
Solve this problem for him.
Input is given from Standard Input in the following format:
N a_1 b_1 : a_{N-1} b_{N-1}
For the lexicographically smallest (A,B), print A and B with a space in between.
7 1 2 2 3 2 4 4 5 4 6 6 7
3 2
We can make a Christmas Tree as shown in the figure below:
8 1 2 2 3 3 4 4 5 5 6 5 7 5 8
2 5
10 1 2 2 3 3 4 2 5 6 5 6 7 7 8 5 9 10 5
3 4