农夫约翰的 $$$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$$$。
在第二个测试用例中,只有一头牛,因此让牛按升序打出所有牌将会清空牌组。
在第三个测试用例中,可以表明不存在允许打出所有牌的有效回合顺序。