32028번 - 이진 검색 트리 복원하기 스페셜 저지

문제

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

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

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

입력

첫 줄에 노드의 개수 N이 주어진다. (1 ≤ N ≤ 200 000)

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

출력

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

복원할 수 있다면 트리의 구조를 N개의 줄에 걸쳐 출력한다.

i번째 줄에는 i번 노드의 왼쪽 자식과 오른쪽 자식의 노드 번호를 출력한다. 자식이 없으면 자식의 노드 번호로 −1을 출력한다.

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

제한

힌트