Hide

Polygraph

On the distant isle of Googlia, there are two cities, Truthtown and Liarville. People from Truthtown always tell the truth and people from Liarville always lie. While exploring Googlia, you have run across a group of N inhabitants, and you want to figure out which city each one came from.

To make life simpler, you begin by numbering these people 1 through $N$. You then question each person, and record their $M$ statements in the short-hand described below.

Short-hand

Meaning

$i$ T $j$

Person $i$ says, "Person $j$ is from Truthtown."

$i$ L $j$

Person $i$ says, "Person $j$ is from Liarville."

$i$ S $j$ $k$

Person $i$ says, "Persons $j$ and $k$ are from the same city."

$i$ D $j$ $k$

Person $i$ says, "Persons $j$ and $k$ are from different cities."

Your task is to deduce which city each person came from. It is guaranteed that there will always be at least one solution.

For example, suppose you were given the following statements: 1 D 2 3, 1 D 2 4, 1 D 3 4, and 2 L 1.

Then, you could reason as follows:

  • There are only two cities, so persons 2, 3, and 4 could not all have come from different cities.

  • Therefore, at least one of person 1’s claims must have been a lie.

  • Therefore, person 1 is from Liartown, and all of his claims must have been lies.

  • Therefore, persons 2, 3, and 4 must all be from the same city.

  • Person 2’s claim is true, so he must be from Truthtown.

  • Therefore, persons 3 and 4 are also from Truthtown.

Input

The first line of the input gives the number of test cases, $T$. $T$ test cases follow. Each case begins with a line containing the integers $N$ and $M$. The following $M$ lines each contain a single statement from one inhabitant, formatted as described above.

You may assume that $1 \leq T \leq 100, 1 \leq i, j, k \leq N$, and $j$ and $k$ are distinct. Furthermore, $1 \leq N \leq 500, 1 \leq M \leq 500$.

Output

For each test case, output one line containing "Case #$X$: $y_1$ $y_2$ ... $y_ N$", where $X$ is the case number (starting from 1) and $y_ i$ is a single letter indicating which city person $i$ is from:

  • If the statements you have been given imply person $i$ must be from Truthtown, then $y_{i}$ should be ’T’.

  • If the statements you have been given imply person $i$ must be from Liarville, then $y_{i}$ should be ’L’.

  • If the statements you have been given are not enough information to determine where person $i$ is from, then $y_ i$ should be ’-’.

Sample Input 1 Sample Output 1
2
4 4
1 D 2 3
1 D 2 4
1 D 3 4
2 L 1
3 1
1 S 1 2
Case #1: L T T T
Case #2: - T -
CPU Time limit 1 second
Memory limit 1024 MB
Statistics Show
Author
License Creative Commons License (cc by)

Please log in to submit a solution to this problem

Log in