Problem J
The Big Mac Question

Sugar Belle: “This apple tree and pear tree are stronger together. They’ll survive whatever comes because they don’t have to do it alone. They belong together. Like your parents. And like us.”

Big McIntosh: “Eeyup.”

Sugar Belle: “Today was a disaster. But today was also the last day we’re ever gonna have to do anything apart. From here on out, we’ll be together. And we’ll make sure everything always works out just right.”

Figure 1: Illustration by Kyle Coate.

At long last, Big Mac and Sugar Belle are getting married. They’ve faced a great many difficulties along the way, but they weathered them together. Before they get married, they wanted to create a keepsake for this momentous occasion: and what better way could they have done that than to follow the passionate elopement of Big Mac’s parents, who planted two trees in secret to commemorate their love for one another?

Big Mac and Sugar Belle did the same. Each of them planted a tree in secret; both trees had $N$ junctions, labeled from $1$ to $N$, connected by $N-1$ branches and were rooted on the ground at the junction labeled $1$. Additionally, in both trees, it was possible to trace a path from the root to any other junction using the branches.

Figure 2: Illustration of Sample Input 1.

To ensure that neither of them would forget what the other’s tree looked like, they did the following: they took out a piece of paper and drew out $N$ junctions, labeled from $1$ to $N$, and labeled its root as the junction labeled $1$. For each of the possible pairs of junctions, if there was a branch between these two junctions in exactly one of the two trees, then they drew a branch connecting these two junctions; otherwise, they didn’t.

Since each of them knows that their own tree looks like, they can easily recover the other’s tree by consulting this drawing. With just the drawing, however, it is not possible to determine the two trees they planted. Hence they could make this drawing public—as an expression of their love—and still share an intimate secret from the world. Isn’t that romantic?

As if by destiny, after doing this, their drawing turned out to be precisely a tree! That is, it also had $N-1$ branches and it was also possible to trace a path from the root to any other junction using the branches. The $i^\text {th}$ of the branches of this tree connected the junctions $A_ i$ and $B_ i$.

You may have stumbled across the drawing that they made. It will not be possible to determine their secret trees with absolute certainty, but perhaps you could do something else—could you find two trees that could have resulted in that drawing?

Input

The first line of input contains a single integer $N$ ($2 \leq N \leq 200\, 000$), the number of junctions in the tree in the drawing.

The next $N-1$ lines of input contain the descriptions of the branches of the tree in the drawing. In particular, the $i^\text {th}$ of these lines contains two integers $A_ i$ and $B_ i$ ($1 \leq A_ i, B_ i \leq N$; $A_ i \neq B_ i$), denoting that the $i^\text {th}$ branch connects junctions $A_ i$ and $B_ i$.

It is guaranteed that it is possible to trace a path from the root to any other junction using the branches.

Output

If there is no way to find two trees consistent with the drawing provided, output a single line containing the string IMPOSSIBLE.

Otherwise, on the first $N-1$ lines, output a possible tree Big Mac could have planted. In particular, the $i^\text {th}$ of these lines should contain two integers $a_ i$ and $b_ i$ ($1 \leq a_ i, b_ i \leq N$; $a_ i \neq b_ i$), denoting that there is a branch between the junctions labeled $a_ i$ and $b_ i$ on Big Mac’s tree. You can output the branches in any order.

On the next $N-1$ lines, output a possible tree Sugar Belle could have planted. In particular, the $i^\text {th}$ of these lines should contain two integers $a’_ i$ and $b’_ i$ ($1 \leq a’_ i, b’_ i \leq N$; $a’_ i \neq b’_ i$), denoting that there is a branch between the junctions labeled $a’_ i$ and $b’_ i$ on Sugar Belle’s tree. You can output the branches in any order.

It should be possible in both trees to trace a path from the root to any other junction using the branches, and these two trees, taken in unison, should produce the provided drawing according to the process described above.

If there are multiple correct answers, you can output any of them.

9
1 2
1 3
2 4
2 5
2 6
3 7
5 8
5 9

1 3
2 3
2 4
3 7
4 5
5 9
6 7
8 9
1 2
2 3
2 5
2 6
4 5
5 8
6 7
8 9

5
1 2
2 3
3 4
4 5

1 2
1 4
3 5
4 5
1 4
2 3
3 4
3 5