P1129 [ZJOI2007] Matrix Game

Little Q is a very smart kid. Besides chess, he also likes a computer puzzle game called the Matrix Game. The game is played on an $n \times n$ black-and-white grid (similar to a chessboard, but colors are arbitrary). Each move allows one of the following operations: - Row swap: choose any two rows of the matrix and swap them (i.e., swap the colors of the corresponding cells). - Column swap: choose any two columns of the matrix and swap them (i.e., swap the colors of the corresponding cells). The goal is to make all cells on the main diagonal (from the top-left corner to the bottom-right corner) black after some number of operations. For some levels, Little Q cannot figure out the solution and starts to suspect that they may be unsolvable. So he decides to write a program to determine whether a given level is solvable.

This problem has multiple test cases. The first line contains an integer $T$, the number of test cases. For each test case: - The first line contains an integer $n$, the size of the grid. - The next $n$ lines each contain $n$ integers, each being 0 or 1, representing the grid. Here, 0 means white and 1 means black.

For each test case, output one line with a single string: output Yes if the level is solvable, otherwise output No.

Constraints - For 20% of the testdata, $n \leq 7$. - For 50% of the testdata, $n \leq 50$. - For 100% of the testdata, $1 \leq n \leq 200$, $1 \leq T \leq 20$. Translated by ChatGPT 5