시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 1024 MB 57 49 45 84.906%

문제

정점이 N개가 있는 트리가 있고 각 정점들은 1부터 N까지 번호가 매겨있다. 해당 트리로부터 (N-2)개의 양의 정수로 이루어진 수열 하나를 다음과 같은 과정을 통해서 만들 것이다.

  1. 차수가 1인 정점들 중에서 번호가 가장 큰 정점을 하나 고른다. 해당 정점을 x라고 부르자.
  2. 정점 x와 인접한 정점의 번호를 수열에 넣는다.
  3. 정점 x와 인접한 간선들을 해당 트리에서 지운다.
  4. 1번부터 3번까지의 과정을 총 (N-2) 번 진행한다.

수열 {a1, ... , aN-2}가 주어졌을 때, 위의 과정을 통해서 이 수열을 만들 수 있는 트리를 구하여라.

입력

다음과 같이 입력이 주어진다.

N
a1 . . . aN-2

출력

해당 트리가 존재한다면 간선 (N-1) 개를 다음 규칙에 만족하게 출력한다.

  • 각 간선은 a b 형태로 출력해야 하며 a < b를 만족하여야 한다.
  • 간선을 사전 순으로 출력해야 한다. 즉, 임의의 두 간선 (a1, b1)과 (a2, b2)에 대해 a1 < a2를 만족하거나 a1a2b1 < b2를 만족하는 경우 (a1, b1) 간선을 (a2, b2) 간선보다 먼저 출력해야 한다.

만약에 트리가 존재하지 않거나 2개 이상 존재하는 경우에는 -1을 출력하여라.

제한

  • 3 ≤ N ≤ 500,000
  • 1 ≤ ai ≤ N (1 ≤ i ≤ N-2)

예제 입력 1

9
9 4 4 5 4 4 6

예제 출력 1

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

예제 입력 2

11
4 3 6 10 2 1 8 9 3

예제 출력 2

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