Problem C
Absurdistan Roads III

Photo by Ivan McClellan

The people of Absurdistan discovered how to build roads only last year. After the discovery, each city decided to build its own road, connecting the city to some other city. Each newly built road can be used in both directions.

You bought a tourist guide which has a map of the country with the newly built roads. However, since you are very interested in history, you would like to know which city built which road.

Given the description of $n$ roads, can you find an assignment of roads to $n$ cities, such that each city built one road? If there are multiple assignments, you are happy with any one. At least one solution is guaranteed to exist.

Input

The first line contains an integer $n$ $(2\le n\le 100\, 000)$ – the number of cities and roads. Then follow $n$ lines with $2$ numbers each. A line containing “$a$ $b$” indicates that there is a road between cities $a$ and $b$, $1 \le a, b\le n, a \not= b$. There can be multiple roads between the same pair of cities.

Output

Print $n$ lines with two integers “$a$ $b$” denoting that a road between $a$ and $b$ was built by city $a$. Each road from the input must appear exactly once in the output. If there are multiple solutions, you can print any one and you can print the roads in any order.

4
1 2
2 3
3 1
4 1

4 1
2 1
3 2
1 3

2
1 2
1 2

2 1
1 2