D2. Дерево с ограничениями
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Требуется построить бинарное дерево из n вершин, удовлетворяющее данным c ограничениям. Пусть вершины искомого бинарного дерева пронумерованы в порядке прямого обхода, начиная с 1. i-е ограничение задано в виде двух номеров ai и bi и направления — влево или вправо. В случае направления влево, bi является вершиной из поддерева с корнем в левом ребенке вершины ai. Аналогично в случае с правым направлением — тогда bi является вершиной из поддерева с корнем в правом ребёнке ai.

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

В первой строке записаны два целых числа n и c. Каждая из следующих c строк содержит 2 целых числа ai, bi (1 ≤ ai, bi ≤ n) и слово "LEFT" или "RIGHT", определяющее, в каком из поддеревьев вершины ai находится вершина bi.

Задача состоит из двух подзадач, которые отличаются друг от друга ограничениями на входные данные. За решение каждой подзадачи вы получите определенное количество баллов. Описание подзадач следует ниже.

  • В подзадаче D1 (9 баллов) будут выполняться следующие ограничения на входные данные: 1 ≤ n ≤ 100, 1 ≤ c ≤ 50.
  • В подзадаче D2 (8 баллов) будут выполняться следующие ограничения на входные данные: 1 ≤ n ≤ 1000000, 1 ≤ c ≤ 100000.
Выходные данные

Ответ должен быть выведен в единственной строке. Принимается любое бинарное дерево, удовлетворяющее данным ограничениям. Вершины дерева должны быть выведены в порядке симметричного обхода с использованием номеров, полученных при прямом обходе дерева.

Если деревьев, удовлетворяющих данным ограничениям, не существует, выведите "IMPOSSIBLE" (без кавычек).

Примеры
Входные данные
3 2
1 2 LEFT
1 3 RIGHT
Выходные данные
2 1 3
Входные данные
3 2
1 2 RIGHT
1 3 LEFT
Выходные данные
IMPOSSIBLE
Примечание

Рассмотрим первый пример. Требуется найти дерево из 3 вершин, удовлетворяющее следующим двум ограничениям. Вершина, получившая номер 2 при прямом обходе дерева должна находиться в левом поддереве вершины, получившей номер 1 при прямом обходе. Вершина, получившая номер 3 при прямом обходе дерева должна находиться в правом поддереве вершины, получившей номер 1. Существует единственное дерево с тремя вершинами, удовлетворяющее этим ограничениям, и его симметричный обход выглядит как (2, 1, 3).

Прямой обход — это обход всех вершин дерева в порядке «корень – левое поддерево – правое поддерево». Симметричный обход — это обход всех вершин дерева в порядке «левое поддерево – корень – правое поддерево». За более подробным описанием можно обратиться к следующему ресурсу: http://algolist.manual.ru/ds/walk.php.