Problem Description

In the Takahashi Kingdom, there are $ N $ villages numbered from $ 1 $ to $ N $. There are roads connecting $ N-1 $ pairs of villages, and any village can be reached from any other village by traversing some roads.

Romeo and Juliet, who live in the Takahashi Kingdom, are planning to move to different villages. They dislike each other and want to live as far apart as possible. Your task is to calculate which villages they should move to in order to maximize the distance between their villages. The distance between two villages is defined as the number of roads that need to be traversed to go from one village to the other.

Input Format

The input is given from the standard input in the following format:

$ N $ $ A_1 $ $ B_1 $ $ A_2 $ $ B_2 $ : $ A_{N-1} $ $ B_{N-1} $

• The first line contains an integer $N\ (2\ ≦\ N\ ≦\ 10^5)$, representing the number of villages in the Takahashi Kingdom.
• The next $ N-1 $ lines contain the information about the roads connecting the villages. The $ i $-th line contains two integers $A_i\ (1\ ≦\ A_i\ ≦\ N)$ and $B_i\ (1\ ≦\ B_i\ ≦\ N)$ separated by a space, indicating that there is a road between village $ A_i $ and village $ B_i $.

Output Format

Output two integers separated by a space on a single line, representing the village numbers where Romeo and Juliet should live to maximize the distance between their villages. If there are multiple possible answers, output any one of them. End the output with a newline.

Sample Input and Output

Sample Input #1

10
7 6
3 2
2 4
4 5
8 9
1 8
1 6
1 2
9 10

Sample Output #1

5 10

Sample Input #2

4
1 2
1 3
1 4

Sample Output #2

4 3

Notes/Hints

Partial Points

This problem has partial points.

• If you correctly solve all test cases where $N\ ≦\ 1,000$, you will be awarded $ 40 $ points.

Sample Explanation 1

In this input, the Takahashi Kingdom has the structure shown in the figure. Outputting "10 5" is also correct.

Sample Explanation 2

In this input, the Takahashi Kingdom has the structure shown in the figure. Outputting "2 3", "3 2", "2 4", "4 2", or "3 4" is also correct.

见题面 Input 部分

见题面 Output 部分