Marathon Route Towns

You are given a series of towns connected by bidirectional roads forming a single path (i.e. a chain). Each connection is represented by a pair of integers, and the entire set of connections gives you a tree with exactly two endpoints (towns with only one connection). Your task is to identify the two endpoints -- the starting town and the ending town of the marathon route.

The input consists of the number of towns followed by exactly n - 1 pairs of integers where each pair represents a connection between two towns. Note that the towns may not be given in numerical order. The output should list the two endpoints in the order in which they first appear in the input when considering only the towns that have a degree of 1.

Note: The problem guarantees that the input graph is a chain, so there will always be exactly two endpoints.

inputFormat

The first line of input contains a single integer n (n ≥ 2), the number of towns. The following n - 1 lines each contain two space-separated integers a and b, representing a bidirectional road (connection) between town a and town b.

outputFormat

Output two space-separated integers representing the starting and ending towns of the marathon route. The starting town is the first town encountered with exactly one connection, and the ending town is the next town encountered with exactly one connection.

5
1 2
2 3
3 4
4 5

1 5