CF1684C Column Swapping

题目描述

如果一个表格每行都单调不降,称它为好的。 给你 $t$ 个 $n_i$ 行 $m_i$ 列的表格,对于每个表格,询问是否能通过调换某两列 **(不一定不同)** 使得这个表格是好的(这样的操作需要且仅能执行一次)。如果可以,输出两列的编号;不可以,输出 $-1$。

输入格式

第一行一个正整数 $t$,表示表格的个数。 接下来输入 $t$ 个表格。 对于每个表格,第一行两个正整数 $n,m$,分别表示表格的行数与列数。 接下来 $n$ 行,每行 $m$ 个正整数,表示这个表格。

输出格式

对于每个表格,单独输出一行,如果能通过上面描述的方式将其变为好的,输出对调的两列的编号;如果不能,输出 $-1$。

说明/提示

$1\le t\le 100$ $1\le n,m\le 2\times 10^5$ $\sum n\times m\le 2\times 10^5$ 表格中的每一个数不超过 $10^9$ **样例解释** **第一个**表格原本就是好的,因此可以将第一列和自己对调。 **第二个**表格中,对调第 $1$ 和第 $2$ 列,会变成 $$1,4$$ $$3,2$$ 不是好的。如果对调任意一列和它自己,就是原本的表格,不是好的。因此输出`-1`。 **第三个**表格中,对调第 $1$,$2$ 列,表格变为 $$1,2$$ $$1,1$$ 是好的。因此输出`1 2`。 **第四个**表格中,调换第 $1$,$3$ 列,表格变为 $$1,2,6$$ $$3,4,5$$ 表格变为好的。输出 `1 3` **最后一个**表格中,每一行只有一个数,是单调不降的,但是只有一列,所以需要将这一列和自己对调。