#P3238. A Coin Game
A Coin Game
Description
Harry and Sally have recently got addicted to a coin game. The game goes as follows.
The games uses a T × T grid board, each square in which is denoted by a pair of integers (x, y) between 1 and T (inclusive). Two players take turns to flip the coins. Each turn a player can choose four coins in the squares (x1, y1), (x1, y2), (x2, y1) and (x2, y2) (1 ≤ x1 < x2 ≤ T, 1 ≤ y1 < y2 ≤ T) to flip, as long as the coin in (x2, y2) will be turned from heads to tails. The player who cannot make a move loses.
After a sweet winning streak, Harry says to Sally, “Let’s have a bet! I’ll play first, and I’ll put heads in some squares and tails in some others of the board. You can decide whether the rest of coins shows heads or tails. I dare say you can’t beat me no matter how you put them.”
Given the squares in which Harry puts heads and those in which he puts tails, can you help Sally decide on the rest of coins so that she will win to teach the arrogant Harry a lesson? Assume that both Harry and Sally play optimally in the game.
Input
The input contains multiple test cases. Each test cases begins with a line containing two integers n1 and n2 (n1, n2 ≤ 200). The next n1 + n2 lines each contain a pair of integers (x, y) (1 ≤ x, y ≤ 100). For the first n1 pairs, Harry puts heads in the corresponding squares. Harry lets Sally decide on coins in the squares denoted by the rest n2 pairs and puts tails in other squares.
Output
For each test case, if Sally can win the game, print “Yes
”, followed by n2 letters being either “H
” (heads) or “T
” (tails), showing one way (possibly among others) she put the coins. The output should be in the same order as the squares appear in the input. If Sally cannot win, just print “No
”.
0 4
1 1
1 2
2 1
2 2
1 1
1 1
2 2
Yes
T
T
T
T
Yes
T
Hint
T is not explicitly given but is assumed to be large enough so that all involved squares lie in the board.
Source
POJ Monthly--2007.06.03, Yao, Jinyu