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 will contain 5 test cases. The first line of a test case will contain two integers $3\le N,M\le 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, that describe a connection between the cogs.

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

The output will contain 5 lines, describing the directions of rotation of cogs identified by $2$ and $3$. Print A for clockwise, B for counter-clockwise, and 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$; and both $2$ and $3$ will always have a path to cog $1$.

Sample Input

3 3
1 2
2 3
3 1
4 4
1 2
2 3
3 4
4 1

Sample Output

LL
BA

Problem Resource: DWITE