Coin Puzzle
Coin Puzzle
Input file: Output file: Time limit: Memory limit:
standard input
standard output
5 seconds
1024 megabytes
Juldys is exploring a dungeon. She has reached a mysterious room, where she finds n coins scattered on the floor, each with unique symbols on both sides. Juldys likes shiny things (and she particularly likes money) so she quickly picks up the coins. But as she collects the first coin, a heavy door slams down behind her, sealing her inside the room.
As she looks around, she sees runes glowing in red on the walls of the room, neatly organised into m rows each consisting of three runes. On closer inspection, she finds that each of the runes matches exactly one of the 2n coin faces! Note that the same rune can appear in several different rows, and that some coin faces may not appear at all.
She also finds a locked door at the far end of the room, with n circular indentations that perfectly fit the coins. When she puts a coin into any of the indentations, all rows containing the rune facing outwards stop glowing, but when the coin is removed they glow once again.
Juldys figures out that she will have to place all n coins in a way that makes all the runes stop glowing, and only then will the door be unlocked. Help her find a way to place the coins, or determine that she is doomed.
Input
The first line of input consists of two space-separated integers, n (3 ≤ n ≤ 22) and m (0 ≤ m ≤ 100), representing the number of coins and the number of rows of runes respectively.
m lines follow, the ith of which contains three space-separated integers, ri,1, ri,2 and ri,3, representing the runes in the ith row. Each ri,j is a nonzero integer between −n and n inclusive, where a positive value k represents the “heads” side of coin k and a negative value −k represents the “tails” side of coin k. You are guaranteed that no two runes in any row refer to the same coin, i.e. that no two of the three values in any row are equal in absolute value.
Output
If Juldys can unlock the door with some configuration of coins, output n space-separated letters, the ith of which is either H or T denoting which side of the ith coin should face up (heads or tails). There may be several correct solutions; any configuration of coins which stops all m rows glowing will be accepted.
If Juldys cannot unlock the door, output the word “Doomed” (without punctuation).
Examples
standard input standard output
|
35
123 |
HTT |
|
38
312 |
Doomed |
Note
For the sample cases, suppose the coins are as follows.
Coin Heads Tails
2cf 3iY
In sample case 1, there are five rows of runes:
Row Runes
4YSc
Placing just the second coin showing tails will stop the second and third rows glowing, as these are the
rows containing f.
Placing the first coin showing heads and the other two showing tails will stop all rows glowing, as all rows
contain at least one out of three displayed runes X, fand Y.
Note that this is not the only valid solution; if all three coins show heads, then X, cand iagain account for all five rows.
|
1 |
X |
S |
|
1 |
X |
c |
i |
|
2 |
X |
f |
i |
|
3 |
X |
i |
f |
|
5 |
X |
c |
i |
In sample case 2, there are eight rows of runes, and no configuration of coins will account for all eight rows.
