DWITE Online Computer Programming Contest


November 2010
Problem 5

A cogwheel is a toothed wheel, ideal for connecting with other cogwheels and assembling machinery. A rotating cogwheel will spin all of the directly connected cogwheels in an opposite direction. However, too many cogwheels can lock up. For example, three cogwheels that are all connected will not be able to move, as some cogwheels will try to spin against each other.

The input file DATA5.txt will contain 5 test cases. The first line of a test case will contain two integers 3 ≤ N, M ≤ 100 separated by a single space. N is the number of unique cogwheels in the system; the system has M connections. The following M lines have a pair of integers separated by a single space, which describes the connection between those two cogs.

Assume that cog #1 is pushed in a clockwise direction and this is the only source of power.

The output file OUT5.txt will contain 5 lines, describing the rotation directions of cogs #2 and #3. Print “A” for clockwise, “B” for counter-clockwise, or “L” if a cog is locked. For example, if cog #2 is rotating clockwise and cog #3 is rotating counter-clockwise, then the output is AB. If both are locked, then the output is LL.

Note: There will always be at least cogs #1, #2, #3. Furthermore, both #2 and #3 will always have a path to cog #1.

Sample Input (first 2 shown):
3 3
1 2
2 3
3 1
4 4
1 2
2 3
3 4
4 1
Sample Output (first 2 shown):