问题 26935. -- 笛卡尔树

26935: 笛卡尔树

时间限制: 3 Sec  内存限制: 128 MB
献花: 18  解决: 8
[献花][花圈]

题目描述

【问题描述】
      笛卡尔树(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),且满足上面三条性质。
     给定一个点,请你构造出一颗笛卡尔树。

输入

第一行是一个整数n(1=<n<=50000),表示给定结点的个数。
接下来n行,每行两个整数k(i),a(i),表示点i的两个权值。题目保证同类权值不出现重复,也就是说对于任意i<>j,一定有k(i)<>k(j),且a(i)<>a(j)。权值都是不超过50000的正整数。

输出

第一行输出解的情况。如果可以构造出一颗笛卡尔树,输出"yes",否则输出"no"。
如果可以构造,那么接下来输出n行,每行3个整数,分别表示第i个结点的父亲、左儿子、右儿子的编号。顶点编号都是从1到n的,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

提示

来源

[献花][花圈]