问题描述

让我们考虑一种特殊类型的二叉搜索树，称为笛卡尔树。回想一下，二叉搜索树是一种有根的有序二叉树，对于它的每个节点(x)，满足以下条件：对于它的每个节点(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)除了主键(k_x)之外，还有一个辅助键，我们将其记为(a_x)，并且这些键满足堆的条件，即：

如果(y)是(x)的父节点，那么(a_y < a_x)

因此，笛卡尔树是一种有根的有序二叉树，它的每个节点都有一对键((k, a))，并且满足上述三个条件。

给定一组键值对，用它们构建一棵笛卡尔树，或者检测是否不可能构建。

输入

输入文件的第一行包含一个整数(N)，即你要用来构建笛卡尔树的键值对的数量（(1 \leq N \leq 50000)）。接下来的(N)行每行包含两个数字，即给定的键值对((k_i, a_i))。对于每个键值对，(\vert k_i \vert, \vert a_i \vert \leq 30000)。所有的主键和所有的辅助键都是不同的，也就是说，对于每个(i \neq j)，有(k_i \neq k_j)且(a_i \neq a_j)。

输出

在输出文件的第一行，如果可以用给定的键值对构建笛卡尔树，打印(YES)；如果不可以，打印(NO)。如果答案是肯定的，在接下来的(N)行输出这棵树。节点从(1)到(N)编号，与输入文件中给出的包含这些键值对的顺序相对应。对于每个节点，输出三个数字，分别是它的父节点、它的左子节点和它的右子节点。如果节点没有父节点或没有对应的子节点，则输出(0)。

输入数据保证只有一棵可能的树。

输入数据 1

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

输出数据 1

YES
2 3 6
0 5 1
1 0 7
5 0 0
2 4 0
1 0 0
3 0 0

来源

2002年东北欧，北部子区域