I Will Be Your Bridge!

Interview

Time limit1sMemory limit512 MB

Summary

A tree lost one edge, splitting it into two components. Print any pair of islands, one from each component, that reconnects the tree.

Level: Medium4 of 10
Topics: Graph, DFS, Union-find, Tree
Solved: No attempts yet

Problem

There are N islands in Seonrin World. The islands are numbered 1, 2, ..., N, one number each. N - 1 bridges connect them, and any two islands can be reached from each other by bridge.

That was true until yesterday.

Wookje, who had been complaining about Seonrin World, saying "Why are there only N - 1 bridges? Traveling is inconvenient," destroyed one bridge! Travel, already inconvenient, became even more inconvenient. Some islands can no longer reach each other. To handle the emergency, the government hired an architect for Seonrin World and ordered them to connect two different islands with a bridge so that again any two islands can be reached from each other.

That architect is you! And you are already busy competing in the world's greatest coding contest...

Input

The first line gives the integer N. (2 ≤ N ≤ 300,000)

The next N - 2 lines give the numbers of the two islands connected by each bridge that Wookje did not destroy.

Output

Print the numbers of the two islands to connect with a bridge. If there are several ways, print any one of them.

Examples3

Example 1
Input
```
4
1 2
1 3
```
Expected output
```
1 4
```
Example 2
Input
```
2
```
Expected output
```
1 2
```
Example 3
Input
```
5
1 2
2 3
4 5
```
Expected output
```
3 4
```