给您一个由 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