Требуется построить бинарное дерево из n вершин, удовлетворяющее данным c ограничениям. Пусть вершины искомого бинарного дерева пронумерованы в порядке прямого обхода, начиная с 1. i-е ограничение задано в виде двух номеров ai и bi и направления — влево или вправо. В случае направления влево, bi является вершиной из поддерева с корнем в левом ребенке вершины ai. Аналогично в случае с правым направлением — тогда bi является вершиной из поддерева с корнем в правом ребёнке ai.
Выходные данные
Ответ должен быть выведен в единственной строке. Принимается любое бинарное дерево, удовлетворяющее данным ограничениям. Вершины дерева должны быть выведены в порядке симметричного обхода с использованием номеров, полученных при прямом обходе дерева.
Если деревьев, удовлетворяющих данным ограничениям, не существует, выведите "IMPOSSIBLE" (без кавычек).
Примечание
Рассмотрим первый пример. Требуется найти дерево из 3 вершин, удовлетворяющее следующим двум ограничениям. Вершина, получившая номер 2 при прямом обходе дерева должна находиться в левом поддереве вершины, получившей номер 1 при прямом обходе. Вершина, получившая номер 3 при прямом обходе дерева должна находиться в правом поддереве вершины, получившей номер 1. Существует единственное дерево с тремя вершинами, удовлетворяющее этим ограничениям, и его симметричный обход выглядит как (2, 1, 3).
Прямой обход — это обход всех вершин дерева в порядке «корень – левое поддерево – правое поддерево». Симметричный обход — это обход всех вершин дерева в порядке «левое поддерево – корень – правое поддерево». За более подробным описанием можно обратиться к следующему ресурсу: http://algolist.manual.ru/ds/walk.php.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 2
1 2 LEFT
1 3 RIGHT
|
2 1 3
|
|
2
|
3 2
1 2 RIGHT
1 3 LEFT
|
IMPOSSIBLE
|