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`
**最后一个**表格中,每一行只有一个数,是单调不降的,但是只有一列,所以需要将这一列和自己对调。