Linear Device#2481
Research Institute of Graph Handling Theory (RIGHT) needs to build a special device for their new experiment. The scheme of this device contains three types of elements: generators, resistors, and transistors. Each generator is connected to exactly one other element, each resistor to two other elements, and each transistor to three elements. There is a special condition: no transistor is connected to another transistor.
All elements must be positioned on a metal string in such a way that any two consecutive elements are connected. Two non-consecutive elements can always be connected by an extra wire. To arrange all elements in this way, the experts from RIGHT invited Vasya from RIGS (Research Institute of Given Strings). But this is not the type of string Vasya is familiar with..., so he asked you for help.
The first line contains the number of elements in the device, (2 \leq N \leq 100000). The next lines describe the elements and their connections. Each line starts with a single letter G, R, or T, representing a Generator, Resistor, or Transistor, respectively. It is followed by one, two, or three numbers, separated by spaces, indicating the numbers of the elements that this element is connected to. The elements are numbered from to in the order of their appearance in the input. An element cannot be connected to itself, and two elements cannot be connected more than once.
The only line of output must contain integer numbers—a permutation of the elements that allows them to be positioned on the metal string so that any two consecutive elements are connected. If there is more than one solution, any will be accepted. If there is no solution, output the single word IMPOSSIBLE.
Beispiel 1