P2594 [ZJOI2009] Coloring Game

There are $n \times m$ coins arranged in an $n \times m$ rectangle. Dongdong and Xixi play a game. In each move, a player may choose a connected component and flip all coins in it, but the move must satisfy: there exists a coin in this component such that all other coins in the component are in its upper-left (including directly to its left or directly above), and this coin is flipped from tails-up to heads-up. Dongdong and Xixi take turns. If a player cannot move, he or she loses. Dongdong moves first. Assuming both play optimally, determine whether Dongdong has a winning strategy.

The first line contains a number $T$, the number of games they play. Then follow $T$ game descriptions. For each game, the first line contains two numbers $n, m$. Then there are $n$ lines, each with $m$ characters. In the $i$-th line, the $j$-th character is `H` if the coin at row $i$, column $j$ is heads-up; otherwise it is tails-up. The upper-left of cell $(i, j)$ refers to the region with row index not exceeding $i$ and column index not exceeding $j$.

For each game, output one line. If Dongdong has a winning strategy, output `-_-`; otherwise, output `=_=`. Note that these are half-width characters, i.e., the three characters have ASCII codes 45, 61, and 95.

For $40\%$ of the testdata, $1 \le n,m \le 5$. For $100\%$ of the testdata, $1 \le n,m \le 100, 1 \le T \le 50$. Translated by ChatGPT 5