13442: 笛卡尔树
Memory Limit：128 MB
Time Limit：3.000 S
Judge Style：Text Compare
Creator：
Submit：2
Solved：0
Description
【问题描述】
笛卡尔树(Cartesian Tree)是一种特殊的二叉搜索树。让我们复习一下：二叉搜索树是一颗有根二叉树，并且对于每个结点x都满足：它左子树中的任何结点的权值都小于x的权值，它右子树中任何结点的权值都大于x的权值。让我们形式化定义：假设x的左子树为L(x)，x的右子树为R(x)，x的权值为k(x)。则一颗满足如下条件的二叉树称为二叉搜索树：
如果点y在L(x)中，则k(y)<k(x)；如果点z在R(x)中，则k(z)>k(x)。
一颗二叉搜索树称为笛卡尔树，当且仅当我们给每个点都附加一个权值a(x)，且每个点的a权值都严格小于它左右子树中的点的a权值。也就是说：如果点y是x的父亲，则a(y)<a(x)。
因此，一颗笛卡尔树就是一颗二叉树，对于每个结点有两个权值(k,a)，且满足上面三条性质。
给定一个点，请你构造出一颗笛卡尔树。
Input
第一行是一个整数n(1=<n<=50000)，表示给定结点的个数。
接下来n行，每行两个整数k(i)，a(i)，表示点i的两个权值。题目保证同类权值不出现重复，也就是说对于任意i<>j，一定有k(i)<>k(j)，且a(i)<>a(j)。权值都是不超过50000的正整数。
Output
第一行输出解的情况。如果可以构造出一颗笛卡尔树，输出"yes"，否则输出"no"。
如果可以构造，那么接下来输出n行，每行3个整数，分别表示第i个结点的父亲、左儿子、右儿子的编号。顶点编号都是从1到n的，0表示空。顶点的输出顺序与输入顺序一致。
Sample Input Copy
7
5 4
2 2
3 9
0 5
1 3
6 6
4 11Sample Output Copy
yes
2 3 6
0 5 1
1 0 7
5 0 0
2 4 0
1 0 0
3 0 0