20131번 - 트리 만들기

문제

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

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

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

입력

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

출력

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

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

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

제한

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

힌트