题目描述

翁老师有一个 $n\times n$ 的棋盘，每个格子有一颗彩色糖果。其中位于 $(i,j)$ 的糖果颜色是 $a_{i,j}$。

翁老师想要知道能否通过重新排列棋盘，使得没有任何一行或一列的糖果颜色完全相同。

输入格式

本题有多组数据

第一行输入一个整数 $t$ 表示测试数据组数。对于每一组数据：

• 第一行输入一个整数 $n$。
• 接下来输入一个 $n\times n$ 的矩阵 $a$。

输出格式

对于每一组数据，若可以通过重排满足条件，则输出 Yes 否则输出 No。

4
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
1
1

Yes
Yes
No
No

提示

样例解释

• 在第一个测试案例中，没有一行或一列包含所有颜色相同的糖果；棋盘可以保持原样。

• 在第二个测试案例中，第一行包含所有颜色为 $1$ 的糖果。可以通过将 $a_{1,1}$ 与 $a_{2,1}$ 对调来重新排列棋盘。重新排列后，棋盘变为

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

现在没有一行或一列是由相同颜色的糖果组成的。

• 在第三个测试案例中，无论棋盘如何重新排列，总会有至少一行或一列由所有颜色为 $1$ 的糖果组成。因此，不存在有效的重新排列。

数据范围

对于 $100\%$ 的数据满足：$1\leq t\leq 500$，$1\le n\leq 100$，$1\leq a_{i,j}\leq n^2$。保证所有测试用例中，$n$ 的总和不超过 $500$。

• 子任务 1 (30分)：$n = 2$ 或 $n = 3$。
• 子任务 2 (30分)：所有糖果的颜色只有两种。
• 子任务 3 (40分)：无特殊限制。