← 返回题目列表

Codeforces · 724/B

B. 批量排序

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

给您一个由 n 行和 m 列组成的表。

每行中的数字形成从 1 到 m 的整数排列。

您可以在一行中选择两个元素并交换它们,但每行不得超过一次。另外,您只能选择两列并交换它们一次。因此,您总共可以执行 0 到 n + 1 个操作。操作可以按任何顺序执行。

你必须检查是否可以在每一行中获得恒等排列 1, 2, ..., m。换句话说,检查是否可以按照给定的规则执行某些操作并使每一行按升序排序。

输入

输入的第一行包含两个整数 n 和 m (1 ≤ n, m ≤ 20) - 给定表中的行数和列数。

接下来的 n 行中的每一行都包含 m 个整数 - 表的元素。保证每行中的数字形成从 1 到 m 的整数排列。

输出

如果有一种方法可以通过遵循给定的规则来获取每行中的恒等排列,则在输出的唯一行中打印“YES”(不带引号)。否则,打印“NO”(不带引号)。

示例

输入 #1

2 4
1 3 2 4
1 3 4 2

输出 #1

YES

输入 #2

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

输出 #2

NO

输入 #3

3 6
2 1 3 4 5 6
1 2 4 3 5 6
1 2 3 4 6 5

输出 #3

YES

注意

在第一个示例中,可以按以下方式操作:

1. 交换第二列和第三列。现在表是 1 2 3 4 1 4 3 2
2. 在第二行中,交换第二个和第四个元素。现在表是 1 2 3 4 1 2 3 4