Terminal Sequence

There is a tree with $N$ vertices. Each vertex has a distinct number from $1$ to $N$. We want to represent this tree as a sequence, as follows.

1. Among the leaf vertices of the tree, remove the one with the smallest number. Then append to the sequence the number of the vertex that was connected to it.
2. Repeat step 1 until only one edge remains.

For example, suppose the tree has edges $(1, 5)$, $(2, 5)$, $(3, 4)$, $(3, 5)$, $(3, 6)$, $(4, 9)$, $(4, 10)$, $(6, 7)$, $(8, 9)$. The vertices are removed in the order $1, 2, 5, 7, 6, 3, 8, 9$, so the sequence is $(5, 5, 3, 6, 3, 4, 9, 4)$.

A tree is uniquely determined by such a sequence. Given the sequence described above, find all edges of the tree.

The first line gives the number of vertices $N$. The second line gives the $N-2$ integers that form the sequence. The input is always such that a tree can be built from it.

Print all edges of the tree, one per line. For each edge, print the vertex with the smaller number first. Print the edges in nondecreasing order of the first number, and if the first numbers are equal, in ascending order of the second number.

• $3 \le N \le 1{,}000$