eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Linear Device

Linear Device

Ліміт часу 1 секунда
Ліміт використання пам'яті 256 MiB

Research Institute of Graph Handling Theory (RIGHT) needs to build a special device to support their new experiment. The scheme of this device contains three types of elements: generators, resistors and transistors. Each generator is connected with exactly one other element, resistor is connected two other elements, and transistor is connected with three of them. There is also a special condition, that no transistor is connected to another transistor.

All elements must be positioned on a metal string in such way that any two subsequent elements must be connected. Two non-subsequent elements are always allowed to be connected by an extra wire. To position all elements on a string in such a way, specialists of RIGHT invited Vasya from RIGS (Research Institute of Given Strings). But this is not a string Vasya used to deal with..., so he asked you for help.

Вхідні дані

The first line contains the number of elements in the device N (2N100000). The next N lines contain descriptions of elements and their connections. Each of them starts with a single letter G, R or T which stands for Generator, Resistor or Transistor respectively. One, two or three numbers follow, separated by spaces, indicating the numbers of elements connected with the corresponding element. Elements are enumerated from 1 to N in order of their description in input. Element cannot be connected to itself, and two elements are not allowed to be connected more than once.

Вихідні дані

The only line of the output must contain N integer numbers - a permutation of elements that allows to position them all on a metal string such that any two consecutive elements are connected. If there is more than one solution, any solution is accepted. If there is no solution, output a single word IMPOSSIBLE.

Приклад

Вхідні дані #1
5
G 2
R 1 3
T 2 4 5
R 3 5
R 3 4
Вихідні дані #1
1 2 3 5 4