Cartesian Tree

Consider a special kind of binary search tree called a Cartesian tree. A binary search tree is a rooted ordered binary tree in which every node $x$ satisfies one condition: every node in its left subtree has a key smaller than the key of $x$, and every node in its right subtree has a key larger than the key of $x$.

Write $L(x)$ for the left subtree of node $x$, $R(x)$ for its right subtree, and $k_x$ for its key. Then every node $x$ satisfies

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

A binary search tree is Cartesian when every node $x$ also carries an auxiliary key $a_x$ and those auxiliary keys satisfy the heap condition, that is,

• if $y$ is the parent of $x$ then $a_y < a_x$

So a Cartesian tree is a rooted ordered binary tree in which every node carries a pair of keys $(k, a)$ and all three conditions above hold.

You are given a set of pairs. Build a Cartesian tree out of them, or decide that it is impossible.

The first line contains an integer $N$, the number of pairs to build the Cartesian tree from ($1 \le N \le 50000$). Each of the next $N$ lines contains two integers $k_i$ and $a_i$. Every pair satisfies $|k_i| \le 30000$ and $|a_i| \le 30000$. All main keys are distinct and all auxiliary keys are distinct, that is, $k_i \ne k_j$ and $a_i \ne a_j$ for $i \ne j$.

On the first line print YES if a Cartesian tree can be built out of the given pairs, or NO if it cannot. If it can, print the tree on the next $N$ lines. Nodes are numbered from 1 to $N$ in the order their pairs appear in the input. For each node print three numbers on one line: its parent, its left child and its right child. Print 0 when the node has no parent or no such child.

Only one tree can be built from the given input.