Polygraph (Small)

The distant island of Googlia has two cities. Everyone from Truthtown always tells the truth, and everyone from Liarville always lies. While exploring Googlia you meet $N$ inhabitants, and you want to work out which city each one comes from.

You first number these people from 1 to $N$. You then question them one by one and record their $M$ statements in the shorthand below.

Deduce which city each person comes from. At least one assignment consistent with all the statements is guaranteed to exist.

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 come from different cities.
• So at least one of person 1's claims is a lie.
• So person 1 is from Liarville, and every claim of person 1 is a lie.
• So persons 2, 3 and 4 all come 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 contains the number of test cases $T$. $T$ test cases follow. The first line of each test case contains the integers $N$ and $M$, separated by a space. The next $M$ lines each contain one statement from one inhabitant, written in the shorthand above.

Limits

• $1 \le T \le 100$
• $1 \le N \le 10$
• $1 \le M \le 500$
• $1 \le i, j, k \le N$
• Within one statement, $j$ and $k$ are different.

For each test case, print one line in the form Case #x: y1 y2 ... yN, where $x$ is the test case number starting from 1 and $y_i$ is a single character telling which city person $i$ comes from. Separate the $N$ characters with one space.

• If the statements imply that person $i$ must be from Truthtown, then $y_i$ is T.
• If they imply that person $i$ must be from Liarville, then $y_i$ is L.
• If the statements are not enough to decide, then $y_i$ is -.