爱丽丝有一块魔法板。该棋盘被描述为 $$$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$$$。
输出
对于每个测试用例,打印“是“如果存在有效的重排,并且”NO”否则。
您可以在任何情况下输出答案(大写或小写)。例如,字符串“是", "是的", "是“,和”是”将被视为积极响应。
示例
输入复制
331 2 33 1 44 1 231 1 12 3 41 4 331 1 11 1 11 1 2
输出复制
YESYESNO
注意
在第一个测试用例中,没有行或列包含所有相同颜色的糖果;董事会可以保持原样。
在第二个测试用例中,第一行由颜色为 $$$1$$$ 的所有糖果组成。可以通过将 $$$a_{1,1}$$$ 与 $$$a_{2,1}$$$ 交换来重新排列棋盘。重新排列后,棋盘变成 $$\begin{matrix} 2 & 1 & 1 \\ 1 & 3 & 4 \\ 1 & 4 & 3 \end{matrix}$$ 现在没有行或列包含所有相同颜色的糖果。
在第三个测试用例中,无论棋盘如何重新排列,总会有至少一行或一列由所有颜色为 $$$1$$$ 的糖果组成。因此,不存在有效的重新排列。