시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB52332963.043%

문제

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 ≤ N ≤ 1,000

예제 입력 1

10
5 5 3 6 3 4 9 4

예제 출력 1

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