단말 수열

$N$개의 정점으로 이루어진 트리가 있다. 이 트리의 정점에는 $1$ 이상 $N$ 이하의 번호가 하나씩 붙어 있다. 이러한 트리를 수열로 표현하려고 한다. 방법은 다음과 같다.

1. 트리의 단말 정점 중 번호가 가장 작은 정점을 제거한다. 그리고 그 정점과 연결되어 있던 정점의 번호를 수열에 추가한다.
2. 간선이 하나 남을 때까지 1번을 반복한다.

예를 들어 트리의 간선이 $(1, 5)$, $(2, 5)$, $(3, 4)$, $(3, 5)$, $(3, 6)$, $(4, 9)$, $(4, 10)$, $(6, 7)$, $(8, 9)$라고 하자. 이때 정점은 $1, 2, 5, 7, 6, 3, 8, 9$ 순서로 제거되므로 수열은 $(5, 5, 3, 6, 3, 4, 9, 4)$가 된다.

이러한 수열로 결정되는 트리는 유일하다. 문제에서 설명한 수열이 주어졌을 때 트리의 간선을 모두 구해보자.

첫째 줄에 정점의 수 $N$이 주어진다. 둘째 줄에는 수열을 이루는 $N-2$개의 정수가 주어진다. 항상 트리를 만들 수 있는 입력만 주어진다.

트리의 모든 간선을 한 줄에 하나씩 출력한다. 간선을 출력할 때는 번호가 작은 정점을 앞에 출력한다. 간선을 앞의 수를 기준으로 비내림차순으로 출력하며, 앞의 수가 같다면 뒤의 수를 기준으로 오름차순으로 정렬해 출력한다.

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