← 返回题目列表

Codeforces · 2208/A

A. 宾果糖果

中文机器翻译题面 查看原题

爱丽丝有一块魔法板。该棋盘被描述为 $$$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”否则。

您可以在任何情况下输出答案(大写或小写)。例如,字符串“是", "是的", "是“,和”是”将被视为积极响应。

示例

输入
复制

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

注意

在第一个测试用例中,没有行或列包含所有相同颜色的糖果;董事会可以保持原样。

在第二个测试用例中,第一行由颜色为 $$$1$$$ 的所有糖果组成。可以通过将 $$$a_{1,1}$$$ 与 $$$a_{2,1}$$$ 交换来重新排列棋盘。重新排列后,棋盘变成 $$\begin{matrix} 2 & 1 & 1 \\ 1 & 3 & 4 \\ 1 & 4 & 3 \end{matrix}$$ 现在没有行或列包含所有相同颜色的糖果。

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