National University of Singapore

Toy Railway

Photo by Robin Webster
Nora is playing with her toy railway. Her railroad network consists of a number of railroad switches connected by tracks. As the network starts to be rather complex, she needs some help with the traffic planning. Write a program that determines how each switch should be set in order for Nora’s train to make the shortest possible loop and return to the starting position.

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.

\includegraphics[width=0.25\textwidth ]{rail1.pdf}
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.

\includegraphics[width=0.5\textwidth ]{rail2.pdf}
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$.


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.


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.

Sample Input 1 Sample Output 1
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
Sample Input 2 Sample Output 2
2 3
1B 1C
1A 2C
2A 2B