카테시안 트리

이진 탐색 트리 중에서 카테시안 트리라고 부르는 특별한 트리를 생각하자. 이진 탐색 트리는 뿌리가 있는 순서 이진 트리이고, 모든 노드 $x$에 대해 왼쪽 서브트리의 모든 노드는 키가 $x$의 키보다 작고 오른쪽 서브트리의 모든 노드는 키가 $x$의 키보다 크다.

노드 $x$의 왼쪽 서브트리를 $L(x)$, 오른쪽 서브트리를 $R(x)$, 키를 $k_x$라고 쓰면 모든 노드 $x$에서 다음이 성립한다.

• $y \in L(x)$이면 $k_y < k_x$
• $z \in R(x)$이면 $k_z > k_x$

카테시안 트리는 여기에 더해 각 노드 $x$에 보조 키 $a_x$가 하나 더 있고, 보조 키가 힙 조건을 만족하는 이진 탐색 트리이다. 즉,

• $y$가 $x$의 부모이면 $a_y < a_x$

정리하면 카테시안 트리는 모든 노드에 두 키의 쌍 $(k, a)$가 붙어 있고 위의 세 조건을 모두 만족하는, 뿌리가 있는 순서 이진 트리이다.

쌍의 집합이 주어진다. 이 쌍들로 카테시안 트리를 만들거나, 만들 수 없다고 판정하라.

첫 줄에 카테시안 트리를 만들 쌍의 개수 $N$이 주어진다 ($1 \le N \le 50000$). 다음 $N$개 줄에는 각각 두 정수 $k_i$와 $a_i$가 주어진다. 모든 쌍에서 $|k_i| \le 30000$, $|a_i| \le 30000$이다. 주 키끼리, 보조 키끼리는 모두 다르다. 즉 $i \ne j$이면 $k_i \ne k_j$이고 $a_i \ne a_j$이다.

첫 줄에 주어진 쌍으로 카테시안 트리를 만들 수 있으면 YES를, 만들 수 없으면 NO를 출력한다. 만들 수 있으면 이어지는 $N$개 줄에 트리를 출력한다. 노드 번호는 입력에 쌍이 주어진 순서대로 1번부터 $N$번까지이다. 각 노드마다 부모, 왼쪽 자식, 오른쪽 자식의 번호를 한 줄에 세 개 출력한다. 부모가 없거나 그 자식이 없으면 0을 출력한다.

주어진 입력으로 만들 수 있는 트리는 하나뿐이다.