P10549 [THUPC 2024 Finals] Simple Game

There are $k$ chessboards. Each chessboard has size $n \times m$. On each chessboard, exactly $3$ positions are $0$, and all other positions are $1$. Now A and B take turns to make moves. In each move, a player must choose one chessboard, and on that chessboard choose a row, or choose a column, or choose both one row and one column, and set all cells in the chosen row and/or column to $0$. However, it must be guaranteed that at least one cell changes between before and after the move. If a player cannot make a move, they lose. Determine whether the first player has a winning strategy.

The first line contains a positive integer $k$, the total number of chessboards. It is guaranteed that $1 \le k \le 10^5$. Then follow $k$ test cases. The $i$-th test case has 4 lines describing the $i$-th chessboard: * Line 1 contains two positive integers $n, m$ separated by spaces, denoting the numbers of rows and columns of the chessboard. It is guaranteed that $1 \le n, m \le 500$. * Lines 2 to 4 each contain two positive integers $x, y$ separated by spaces, indicating a position whose value is $0$ on this chessboard. These positions are guaranteed to be pairwise distinct, and $1 \leq x \leq n$, $1 \leq y \leq m$.

If the first player has a winning strategy, output the string `OvO`. Otherwise, output the string `QAQ`.

Initially, the chessboard is: ``` 011 001 ``` The first player only needs to select row 1 and column 2 to clear everything to $0$, so the second player cannot make a move. Therefore, the first player wins. **Source and Acknowledgements** From the THUPC2024 (Tsinghua University Student Programming Contest and Collegiate Invitational) Finals. Thanks to THUSAA for providing the problem. For the testdata, statement, reference solution, editorial, etc., please refer to the THUPC official repository . Translated by ChatGPT 5