트리 만들기
시간 제한2초메모리 제한1024 MB
항상 가장 큰 번호의 리프를 제거하는 규칙으로 만들어진 수열이 주어질 때, 이 수열을 만드는 트리가 정확히 하나 존재하는지 판정하고 그 트리의 간선을 사전순으로 출력하며, 아니면 -1을 출력한다.
문제
정점이 N개 있고 각 정점에 1부터 N까지 번호가 붙은 트리가 있다. 이 트리로부터 (N-2)개의 양의 정수로 이루어진 수열을 다음 과정으로 만든다.
- 차수가 1인 정점 중 번호가 가장 큰 정점을 하나 고른다. 이 정점을 x라고 하자.
- 정점 x와 인접한 정점의 번호를 수열에 넣는다.
- 정점 x와 인접한 간선을 트리에서 지운다.
- 1번부터 3번까지의 과정을 총 (N-2)번 진행한다.
수열 {a1, ..., aN-2}가 주어졌을 때, 위 과정으로 이 수열을 만들 수 있는 트리를 구하여라.
입력
다음과 같이 입력이 주어진다.
N
a1 . . . aN-2
출력
해당 트리가 존재하면 간선 (N-1)개를 다음 규칙에 맞게 출력한다.
- 각 간선은 a b 형태로 출력해야 하며 a < b를 만족해야 한다.
- 간선을 사전 순으로 출력해야 한다. 즉, 임의의 두 간선 (a1, b1)과 (a2, b2)에 대해 a1 < a2이거나 a1 = a2, b1 < b2이면 (a1, b1) 간선을 (a2, b2) 간선보다 먼저 출력해야 한다.
트리가 존재하지 않거나 2개 이상 존재하면 -1을 출력하여라.
제한
- 3 ≤ N ≤ 500,000
- 1 ≤ ai ≤ N (1 ≤ i ≤ N-2)