Polygraph (Large)

On the distant island of Googlia there are two cities, Truthtown and Liarville. Everyone from Truthtown always tells the truth, and everyone from Liarville always lies. While exploring Googlia you have met a group of N inhabitants, and you want to work out which city each one came from.

Number the inhabitants 1 through N. You question each of them and record their M statements in the shorthand below.

A person may talk about themselves, so i can be equal to j or to k. At least one assignment of cities that agrees with every statement always exists.

Decide, for each inhabitant, which city they came from.

For example, suppose the statements are 1 D 2 3, 1 D 2 4, 1 D 3 4, and 2 L 1. Then you can reason as follows.

• There are only two cities, so persons 2, 3, and 4 cannot all have come from different cities.
• So at least one of person 1's claims is a lie.
• So person 1 is from Liarville, and every one of person 1's claims is a lie.
• So persons 2, 3, and 4 all came from the same city.
• Person 2's claim is true, so person 2 is from Truthtown.
• So persons 3 and 4 are from Truthtown as well.

The first line holds the number of test cases, T. T test cases follow. Each case begins with a line holding the integers N and M. The next M lines each hold one statement from one inhabitant, written in the shorthand above.

Limits

• 1 ≤ T ≤ 100
• 1 ≤ N ≤ 500
• 1 ≤ M ≤ 500
• 1 ≤ i, j, k ≤ N
• j and k are different

For each test case print one line of the form "Case #x: y1 y2 ... yN", where x is the case number starting from 1 and yi is a single letter for inhabitant number i.

• Print T if the statements force person i to be from Truthtown.
• Print L if the statements force person i to be from Liarville.
• Print - if the statements leave both cities possible for person i.

Separate the letters with a single space.