Задача №2781. Декартово дерево

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

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

В первой строке записано число \(N\) — количество пар. Далее следует \(N\) (\(1 \le N \le 50\,000\)) пар \((a_i, b_i)\). Для всех пар \(\lvert a_i\rvert, \lvert b_i \rvert \le 30\,000\). \(a_i \ne a_j\) и \(b_i \neq b_j\) для всех \(i \ne j\).

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

Если декартово дерево с таким набором ключей построить возможно, выведите в первой строке YES, в противном случае выведите NO. В случае ответа YES, выведите \(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
Сдать: для сдачи задач необходимо войти в систему