CF2208A.Bingo Candies

Alice has a magic board. The board is described as a $n\times n$ grid; each tile has a colored candy in it. The color of the candy in the $i$-th row, $j$-th column is $a_{i,j}$.

Bob wants to know if he can rearrange the board in some way so that no row or column consists of $n$ candies of the same color.

Your task is to determine whether such a rearrangement exists.

爱丽丝有一块魔法板。该板被描述为一个 $n\times n$ 的网格；每个格子中都有一颗彩色糖果。第 $i$ 行、第 $j$ 列格子中的糖果颜色为 $a_{i,j}$。

鲍勃想知道：能否以某种方式重新排列这块板，使得没有任何一行或一列包含 $n$ 颗同色糖果？

你的任务是判断这样的重新排列是否存在。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 500$). The description of the test cases follows.

The first line of each test case contains an integer $n$ ($1\le n\le 100$), denoting the size of the board.

The following $n$ lines contain $n$ integers each; the $j$-th integer on the $i$-th line is $a_{i,j}$ ($1\le a_{i,j}\le n^2$), denoting the color of candies on the board.

It is guaranteed that the sum of $n$ over all test cases does not exceed $500$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 500$）。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1\le n\le 100$），表示棋盘的大小。

接下来的 $n$ 行，每行包含 $n$ 个整数；其中第 $i$ 行的第 $j$ 个整数为 $a_{i,j}$（$1\le a_{i,j}\le n^2$），表示棋盘上该位置糖果的颜色。

保证所有测试用例的 $n$ 值之和不超过 $500$。

For each test case, print "YES" if a valid rearrangement exists, and "NO" otherwise.

You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

对于每个测试用例，如果存在合法的重排方案，则输出 “YES”；否则输出 “NO”。

你可以以任意大小写形式输出答案（大写或小写均可）。例如，字符串 “yEs”、“yes”、“Yes” 和 “YES” 均会被识别为肯定回答。

In the first test case, no row or column consists of all candies with the same color; the board can be left as it is.

In the second test case, the first row consists of all candies of color $1$. The board can be rearranged by swapping $a_{1,1}$ with $a_{2,1}$. After the rearrangement, the board becomes $$ \begin{matrix} 2 & 1 & 1 \\ 1 & 3 & 4 \\ 1 & 4 & 3 \end{matrix} $$ Now no row or column consists of all candies with the same color.

In the third test case, no matter how the board is rearranged, there will always be at least one row or column consisting of all candies of color $1$. Therefore, there is no valid rearrangement.

在第一个测试用例中，不存在任何一行或一列由同一种颜色的糖果组成；因此棋盘可保持原状。

在第二个测试用例中，第一行全部由颜色为 $1$ 的糖果组成。可通过交换 $a_{1,1}$ 与 $a_{2,1}$ 来重新排列棋盘。重排后，棋盘变为

$$\begin{matrix} 2 & 1 & 1 \\ 1 & 3 & 4 \\ 1 & 4 & 3 \end{matrix}$$

此时，不存在任何一行或一列由同一种颜色的糖果组成。

在第三个测试用例中，无论怎样重排棋盘，总至少存在一行或一列全部由颜色为 $1$ 的糖果组成。因此，不存在合法的重排方案。