12602번 - Polygraph (Large) 다국어채점 준비 중

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.

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.

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.

Limits

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

For each test case, output one line containing "Case #x: y₁ y₂ ... 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 '-'.