← 返回题目列表

Codeforces · 2060/B

B. 农夫约翰的纸牌游戏

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

农夫约翰的 $$$n$$$ 奶牛正在玩纸牌游戏! Farmer John 有一副 $$$n \cdot m$$$ 卡片,编号从 $$$0$$$ 到 $$$n \cdot m-1$$$。他向他的每头 $$$n$$$ 奶牛分发 $$$m$$$ 卡片。

Farmer John 希望游戏公平,因此每头牛每轮只能打出 $$$1$$$ 卡。他决定确定一个回合顺序,由长度为 $$$n$$$ 的排列$$$^{\text{*}}$$$ $$$p$$$ 确定,这样第 $$$p_i$$$ 头牛将成为在一轮中将牌放在中心堆顶部的第 $$$i$$$ 头牛。

换句话说,每轮中以下事件按顺序发生:

- 第 $$$p_1$$$ 头牛将牌组中的任何牌放在中间牌堆的顶部。
- 第 $$$p_2$$$ 头牛将牌组中的任何牌放在中间牌堆的顶部。
- ...
- 第 $$$p_n$$$ 头牛将牌组中的任何牌放在中间牌堆的顶部。

有一个问题。最初,中心堆包含一张编号为 $$$-1$$$ 的卡片。为了放置卡片,卡片的数量必须大于中心堆顶部的卡片的数量。然后,新放置的牌成为中心牌堆的顶牌。如果一头牛无法将任何牌放入其牌库中,则游戏被视为失败。

Farmer John 想知道:是否存在 $$$p$$$ 使得他的所有奶牛在玩完所有 $$$m$$$ 轮游戏后有可能清空它们的甲板?如果是,则输出任何有效的 $$$p$$$。否则,输出$$$-1$$$。

输入

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

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \leq n \cdot m \leq 2\,000$$$) — 牛的数量和每头牛收到的卡片数量。

以下 $$$n$$$ 行每行包含 $$$m$$$ 个整数 – 每头牛收到的卡片。保证所有给定的数字(在所有 $$$n$$$ 行中)都是不同的,并且范围从 $$$0$$$ 到 $$$n \cdot m - 1$$$(含)。

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

输出

对于每个测试用例,在新行中输出以下内容:

- 如果 $$$p$$$ 存在,则输出 $$$n$$$ 空格分隔的整数 $$$p_1, p_2, \ldots, p_n$$$。
- 否则,输出$$$-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

注意

在第一个测试用例中,允许打出所有牌的一个回合顺序是让第一头牛先于第二头牛走。打出的牌将为$$$0\rightarrow1\rightarrow2\rightarrow3\rightarrow4\rightarrow5$$$。

在第二个测试用例中,只有一头牛,因此让牛按升序打出所有牌将会清空牌组。

在第三个测试用例中,可以表明不存在允许打出所有牌的有效回合顺序。