Problem D
Toy Railway

Photo by Robin Webster

Each switch looks as in Figure 1 and can be set to either of two states: B or C. If the trains enters at A it goes to B or C depending on the state of the switch. On the other hand, if the train enters at B or C, it always goes to A regardless of the state of the switch.

Figure 1: Labelling of the three connection points of a switch.

The starting position of Nora’s train is such that it is entering switch 1 at point A. The program should find static switch settings that make the train return to the starting position, faced in the same direction, while passing as few switches as possible, or determine that it is impossible. The train may travel on the same track multiple times (in different directions), but can never be reversed.

Figure 2: The railway network in the first example below. The shortest loop contains 8 switches: $1\rightarrow 2\rightarrow 3\rightarrow 7\rightarrow 8\rightarrow 9\rightarrow 10 \rightarrow 6 \rightarrow 1$. There are several loops containing 9 switches, for example $1\rightarrow 2\rightarrow 3\rightarrow 1\rightarrow 6\rightarrow 4\rightarrow 5\rightarrow 4\rightarrow 6 \rightarrow 1$.

Input

The first line of the input contains two integers $N$ and $M$, the number of switches and the number of connections, respectively, where $1\le N \le 100\, 000$ and $1 \le M \le 150\, 000$. Then $M$ rows follow, each containing two strings: the labels of two distinct connection points that are connected by track. Each label consists of an integer between $1$ and $N$ identifying the switch, and then a letter A, B or C, identifying the specific connection point, according to Figure 1. All tracks can be traveled in both directions. No label occurs more than once and all labels do not have to occur (there may be dead ends and even disconnected parts of the network). A track may connect two points on the same switch. The network does not have to be realizable on a plane; Nora likes building in several levels.

Output

If a solution exists, output a string of $N$ characters, each being either B or C and giving the state of switch $1,2,...,N$, respectively. If there are multiple solutions, any one of them will be accepted. If no solution exists, output the string “Impossible”.

Note that there are many possible solutions in the first example below: only the states of switches $1$, $3$, $9$ and $10$ matter.

10 13
1B 2B
1C 3C
3A 2A
4B 5B
4C 5A
1A 6A
6C 4A
3B 7B
7A 8C
8A 9A
9C 10A
10C 6B
10B 5C

BCBBBBBBCC

2 3
1B 1C
1A 2C
2A 2B

Impossible