시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 1024 MB | 52 | 33 | 29 | 63.043% |
N개의 정점으로 이루어진 트리가 있다. 이 트리의 정점에는 1보다 크거나 같고, N보다 작거나 같은 번호가 하나씩 붙어있다. 이러한 형태의 트리를 수열로 표현하려고 한다. 그 방법은 다음과 같다.
예를 들어, 트리의 간선이 (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개의 정수가 주어진다. 항상 트리를 만들 수 있는 입력만 주어진다.
트리의 모든 간선을 한 줄에 하나씩 출력한다. 간선을 출력할 때는 정점 번호가 작은 것을 앞에 출력한다. 간선을 앞의 수를 기준으로 비내림차순으로 출력하며, 앞의 수가 같다면 뒤의 수로 오름차순 정렬해 출력한다.
10 5 5 3 6 3 4 9 4
1 5 2 5 3 4 3 5 3 6 4 9 4 10 6 7 8 9