405000: GYM101733 F Network Topology

The Alexander's distributed computational system consists of n computers which are connected in a network with n - 1 wires. Each pair of computers is directly or indirectly (via other computers) connected by these wires.

Alexander is worried about the safety of the data in the system. He plans to add the extra HDDs into two storage computers. The distance between two computers is the minimum possible number of wires that is required to get data from one computer to the other. When Alexander picks two computers, for each computer in his network he computes the minimum possible distance to the storage. Unreliability of the whole network is equal to the maximum value of this minimum distance among all computers in the network.

Help Alexander and find two different computers which should be used to install additional hard drives in order to achieve minimum value of unreliability.

The first input line contains one integer n (2 ≤ n ≤ 200 000), number of computers in the Alexander's system. Each of the next n - 1 lines contains two integers x y (1 ≤ x, y ≤ n, x ≠ y), the indices of computers connected by the direct connection.

Print the indices of two different selected computers. If there are multiple correct solutions, print any of them.

3
1 2
2 3

3 1

6
1 2
3 2
2 4
4 5
4 6

2 4