이진 검색 트리 복원하기

면접 대비

시간 제한2초메모리 제한1024 MB

요약

각 노드의 값과 깊이가 주어질 때 이진 탐색 트리를 복원합니다. 가능한 트리가 없으면 -1을 출력합니다.

난이도: 보통10점 중 6점
유형: 정렬, 분할 정복, 트리
정답자: 아직 제출이 없습니다

문제

찬솔이는 $N$ 개의 노드에 정수가 적혀 있는 이진 검색 트리를 만들었다. 이진 검색 트리는 모든 노드 $i$ 에 대해, $i$ 의 왼쪽 자손 노드에 적힌 수가 모두 $i$ 에 적힌 수보다 작고, $i$ 의 오른쪽 자손 노드에 적힌 수가 모두 $i$ 에 적힌 수보다 큰 이진 트리이다.

찬솔이는 모든 $i$ 에 대해 이진 검색 트리의 $i$ 번 노드의 깊이 $H_i$ 와 $i$ 번 노드에 적힌 정수 $A_i$ 를 기록해 두었다. 이때 $A_i$ 는 모두 다르고, 루트 노드의 깊이는 1이다. ( $1 \le i \le N$ )

찬솔이는 ICPC World Finals에 다녀오는 동안 이진 검색 트리를 잃어버렸다. 기록해 둔 정보를 이용해 이진 검색 트리를 복원하자.

입력

첫 줄에 노드의 개수 $N$ 이 주어진다. ( $1 \le N \le 200000$ )

둘째 줄부터 $N$ 개의 줄에 걸쳐 트리의 노드 정보가 주어진다. 모든 $1 \le i \le N$ 에 대해, $(i+1)$ 번째 줄에는 $i$ 번 노드에 적힌 정수 $A_i$ 와 $i$ 번 노드의 깊이 $H_i$ 가 공백으로 구분되어 주어진다. ( $-2 \cdot 10^9 \le A_i \le 2 \cdot 10^9$ , $1 \le H_i \le N$ ) $A_i$ 는 모두 다르다.

출력

주어진 기록으로 이진 검색 트리를 복원할 수 없다면 -1을 출력한다.

복원할 수 있다면 트리의 구조를 $N$ 개의 줄에 걸쳐 출력한다. $i$ 번째 줄에는 $i$ 번 노드의 왼쪽 자식과 오른쪽 자식의 노드 번호를 출력한다. 자식이 없으면 그 자리에 -1을 출력한다.

복원할 수 있는 트리가 여러 개라면 아무거나 복원해도 된다.

예제4

예제 1
입력
```
3
1 2
2 1
3 2
```
예상 출력
```
-1 -1
1 3
-1 -1
```
예제 2
입력
```
3
1 1
2 2
3 2
```
예상 출력
```
-1
```
예제 3
입력
```
3
2 2
5 3
4 2
```
예상 출력
```
-1
```
예제 4
입력
```
3
100 2
200 1
300 2
```
예상 출력
```
-1 -1
1 3
-1 -1
```