← 返回题目列表

Codeforces · 1684/C

C. 列交换

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

为您提供一个包含 $$$n$$$ 行和 $$$m$$$ 列的网格,其中每个单元格上都写有一个正整数。如果每一行中的数字序列都按非递减顺序排序,那么我们称网格为好的网格。这意味着,对于每个 $$$1 \le i \le n$$$ 和 $$$2 \le j \le m$$$,以下内容成立:$$$a_{i,j} \ge a_{i, j-1}$$$。

您必须执行以下操作一次:选择索引为 $$$i$$$ 和 $$$j$$$ (不一定不同)的两列,$$$1 \le i, j \le m$$$,然后交换它们。

系统会要求您确定交换后网格是否可以恢复正常,如果可以,则找到需要交换的列。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 100$$$)。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n, m \le 2 \cdot 10^5$$$) - 分别是行数和列数。

接下来的 $$$n$$$ 行包含 $$$m$$$ 整数,$$$i$$$ 行的第 $$$j$$$ 元素为 $$$a_{i,j}$$$ ($$$1 \le a_{i,j} \le 10^9$$$) — 写入第 $$$j$$$ 单元格的数字$$$i$$$第行。

保证所有测试用例的 $$$n \cdot m$$$ 之和不超过 $$$2 \cdot 10^5$$$。

输出

如果交换后无法得到好的网格,则输出$$$-1$$$。

在另一种情况下,输出 $$$2$$$ 整数 - 应该交换以获得良好网格的列的索引。

如果有多个解决方案,请打印其中一个。

示例

输入 #1

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

输出 #1

1 1
-1
1 2
1 3
1 1

注意

在第一个测试用例中,网格最初是好的,因此我们可以,例如,将第一列与其自身交换。

在第二个测试用例中,不可能使网格良好。

在第三个测试用例中,需要交换第一列和第二列,然后网格就变好了。