CF2060B Farmer John's Card Game

题目描述

农夫约翰的卡牌游戏

农夫约翰的 $n$ 头奶牛正在玩一个卡牌游戏！农夫约翰有一副包含 $n \cdot m$ 张卡牌的牌组，编号从 $0$ 到 $n \cdot m - 1$。他给每头奶牛分发 $m$ 张卡牌。

农夫约翰希望游戏公平，因此每头奶牛每轮只能出一张牌。他决定确定一个轮次顺序，由一个长度为 $n$ 的排列 $^{\text{*}} p$ 决定，使得第 $p_i$ 头奶牛将是第 $i$ 头奶牛在一轮中将牌放在中心堆上的顺序。

换句话说，在每轮中，按顺序发生以下事件：

1. 第 $p_1$ 头奶牛从他们的牌堆中放置任意一张牌到中心堆的顶部。
2. 第 $p_2$ 头奶牛从他们的牌堆中放置任意一张牌到中心堆的顶部。
3. ...
4. 第 $p_n$ 头奶牛从他们的牌堆中放置任意一张牌到中心堆的顶部。

有一个限制。最开始，中心堆顶部的卡牌编号为 $-1$。为了放置一张牌，放置的牌的编号必须大于中心堆顶部的牌的编号。然后，新放置的牌将成为中心堆的顶部牌。如果一头奶牛无法放置任何牌，则游戏被视为失败。

农夫约翰想知道：是否存在一个 $p$，使得所有奶牛在玩完所有 $m$ 轮后能够清空他们的牌堆？如果存在，输出任意有效的 $p$。否则，输出 $-1$。

$^{\text{*}}$ 长度为 $n$ 的排列包含从 $1$ 到 $n$ 的每个整数恰好一次。

输入格式

第一行包含一个整数 $t$ （$1 \leq t \leq 400$）——测试用例的数量。

每个测试用例的第一行包含两个整数 $n$ 和 $m$ （$1 \leq n \cdot m \leq 2000$）——奶牛的数量和每头奶牛收到的卡牌数量。

接下来的 $n$ 行中，每行包含 $m$ 个整数，表示每头奶牛收到的卡牌。保证所有给定的数字（在所有 $n$ 行中）都是不同的，并且在 $0$ 到 $n \cdot m - 1$ 的范围内。

保证所有测试用例中 $n \cdot m$ 的总和不超过 $2000$。

输出格式

对于每个测试用例，在新的一行输出以下内容：

• 如果 $p$ 存在，输出 $n$ 个以空格分隔的整数 $p_1, p_2, \ldots, p_n$。
• 否则，输出 $-1$。

样例 1

样例输入 1

4
2 3
0 4 2
1 5 3
1 1
0
2 2
1 2
0 3
4 1
1
2
0
3

样例输出 1

1 2
1
-1
3 1 2 4

输入输出样例 1

4
2 3
0 4 2
1 5 3
1 1
0
2 2
1 2
0 3
4 1
1
2
0
3

1 2
1
-1
3 1 2 4

说明/提示

在第一个测试用例中，可以通过让第一头奶牛在第二头奶牛之前出牌来实现所有牌的出牌顺序。出牌顺序将是 $ 0 \rightarrow 1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 5 $。

在第二个测试用例中，只有一头奶牛，因此让这头奶牛按递增顺序出牌将清空牌堆。

在第三个测试用例中，可以证明不存在有效的出牌顺序使得所有牌都能被出牌。