4320 - 第八课:笛卡尔树

让我们考虑一种特殊的二叉查找树,叫做笛卡尔树。回想一下,二叉查找树是有根有序的二叉树,这样,对于它的每一个节点x满足以下条件:在它的左子树的每个节点的数值小于x的数值,它的右子树的每个节点的数值大于x的数值。也就是说,如果我们用L(x)表示结点x的左子树,用R(x)表示结点x右子树,用$ k_x $表示该结点x的数值,那么对每个结点x我们有

  如果y ∈ L(x),那么$ k_y \lt k_x $

  如果z ∈ R(x),那么$ k_z \gt k_x $

  若一棵二叉查找树被称为笛卡尔树,那么它的每一个结点x除了主要数值$ k_x $外还有一个附加数值$a_x$,且这个数值符合堆的条件,即

  如果y是x的父亲,那么$a_y < a_x$

  因此,一棵笛卡尔树是一棵有根有序的二叉树,这样,它的每个节点拥有两个数值(k , a)和满足上述的三个条件。

  给出一系列点,构建出它们的笛卡尔树,或检测构建出它们的笛卡尔树是不可能的。

输入

第一行包括一个整数$ N(1 \le N \le 50 000) $,表示你要构建的笛卡尔树的点的对数。

接下来N行,每行有两个数字$ k_i,a_i,|k_i|, |a_i| \le 30 000 $,描述第i个结点信息。

保证每行的k和a是不同的:$ 若i \ne j则k_i \ne k_j 并且 a_i \ne a_j $。

输出

如果能构建出笛卡尔树则在第一行输出YES否则输出NO。

如果是YES,则在接下来N行输出这棵树。第$i(1 \le i \le N)$行输出第i个结点的父亲,左儿子,右儿子。如果这个结点无父亲或者儿子,则用0代替。

输入保证能构建出笛卡尔树的只有一种情况。

样例

输入

7
5 4
2 2
3 9
0 5
1 3
6 6
4 11

输出

YES
2 3 6
0 5 1
1 0 7
5 0 0
2 4 0
1 0 0
3 0 0
时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题