Absurdistan Roads III

The people of Absurdistan learned how to build roads only last year. Since then, every city has built exactly one road, joining that city to some other city. Every new road can be travelled in both directions.

The tourist guide you bought contains a map with all of the new roads. The map shows the roads only, not which city built which road. You are interested in history, so you want to recover that correspondence.

Given the description of $n$ roads, assign the roads to the $n$ cities so that each city built exactly one road. At least one such assignment exists.

The first line contains an integer $n$, the number of cities and also the number of roads. ($2 \le n \le 100000$)

Each of the next $n$ lines contains two integers $a$ and $b$, meaning that a road joins city $a$ and city $b$. ($1 \le a, b \le n$, $a \ne b$)

Several roads may join the same pair of cities.

Print $n$ lines. The $i$-th line contains two integers $i$ and $b$, meaning that city $i$ built the road whose other endpoint is city $b$. Every road of the input must appear exactly once in the output.

If several assignments are possible, print the one whose sequence $b_1, b_2, \dots, b_n$ is lexicographically smallest.