CF274D Lovely Matrix

Lenny 有一个 $n \times m$ 的正整数矩阵。他非常喜欢这个矩阵，因为矩阵的每一行都是非递减排序的。出于同样的原因，他把这样的整数矩阵称为“lovely”矩阵。 有一天，Lenny 在学校时，他的弟弟在家里玩弄了这个矩阵。他擦掉了矩阵中的一些元素，并且改变了部分列的顺序。当 Lenny 回到家时，他非常伤心。现在 Lenny 想重新恢复他的矩阵。 请你帮助他找到一种重新排列矩阵列的顺序，使得可以补全被擦掉的元素，从而重新获得一个“lovely”矩阵。注意，你可以用任意整数填补被擦掉的元素。

输入的第一行为两个正整数 $n$ 和 $m$（$1 \leq n \cdot m \leq 10^{5}$）。接下来的 $n$ 行，每行包含 $m$ 个用空格分隔的整数，表示该矩阵。整数 $-1$ 表示该位置上的元素被擦掉。其他整数（每个都在 $0$ 到 $10^{9}$ 之间，包括 $0$ 和 $10^{9}$）表示已经填好的元素。

如果不存在可行的列重排方式，输出 $-1$。否则，输出 $m$ 个整数 $p_1, p_2, \ldots, p_m$，表示所求的列的排列。也就是说，恢复后的第一列为原矩阵的第 $p_1$ 列，第二列为原矩阵的第 $p_2$ 列，依此类推。

由 ChatGPT 5 翻译