e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more
Problems

Декартово дерево

Декартово дерево

Вам даны пары чисел (ai, bi), Вам необходимо построить декартово дерево, такое что i-ая вершина имеет ключи (ai, bi), вершины с ключом ai образуют бинарное дерево поиска, а вершины с ключом bi образуют кучу.

Входные данные

В первой строке записано число N - количество пар. Далее следует N (1N50000) пар (ai, bi). Для всех пар |ai|, |bi| 30000. aiaj и bibj для всех ij.

Выходные данные

Если декартово дерево с таким набором ключей построить возможно, выведите в первой строке YES, в противном случае выведите NO. В случае ответа YES, выведите N строк, каждая из которых должна описывать вершину. Описание вершины состоит из трёх чисел: номер предка, номер левого сына и номер правого сына. Если у вершины отсутствует предок или какой-либо из сыновей, то выводите на его месте число 0. Если подходящих деревьев несколько, выведите любое.

Time limit 2 seconds
Memory limit 64 MiB
Input example #1
7
5 4
2 2
3 9
0 5
1 3
6 6
4 11
Output example #1
YES
2 3 6
0 5 1
1 0 7
5 0 0
2 4 0
1 0 0
3 0 0