题目描述

Alice 有一块魔法棋盘。棋盘是一个 $n\times n$ 的网格，每个格子里有一颗有颜色的糖果。第 $i$ 行第 $j$ 列的糖果颜色用 $a_{i,j}$ 表示。

Bob 想知道，是否存在一种重排棋盘的方法，使得没有任何一行或一列由 $n$ 颗同色的糖果组成。

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

输入格式

每组测试数据包含多组测试用例。第一行包含测试用例数量 $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$。

输出格式

对于每组测试用例，若存在满足条件的棋盘重排，输出 "YES"；否则输出 "NO"。

输出时大小写不敏感。例如，"yEs"、"yes"、"Yes" 和 "YES" 都被认为是肯定的回答。

说明/提示

在第一组测试用例中，没有任何一行或一列的糖果颜色全部相同，因此可直接保留原棋盘即可。

在第二组测试用例中，第一行全部为颜色 $1$。通过交换 $a_{1,1}$ 与 $a_{2,1}$，可以重排棋盘。重排后棋盘如下：

现在没有任何一行或一列全部由同色糖果组成。

在第三组测试用例中，无论如何重排，始终会有一行或一列全部由颜色 $1$ 构成。因此不存在满足条件的重排。

由 ChatGPT 5 翻译

样例

3
3
1 2 3
3 1 4
4 1 2
3
1 1 1
2 3 4
1 4 3
3
1 1 1
1 1 1
1 1 2

YES
YES
NO