给出一个 $N$ 行 $M$ 列的矩阵A, 保证满足以下性质:
- $M > N$。
- 矩阵中每个数都是 $[0, N]$ 中的自然数。
- 每行中, $[1, N]$ 中每个自然数都恰好出现一次。这意味着每行中 $0$ 恰好出现 $M - N$ 次。
- 每列中,$[1, N]$ 中每个自然数至多出现一次。
现在我们要在每行中选取一个非零数,并把这个数之后的数赋值为这个数。我们希望保持上面的性质4,即每列中,$[1, N]$ 中每个自然数仍然至多出现一次。
输入格式
第一行一个正整数 $T$,表示数据组数。
后面包含 $T$ 组数据,各组数据之间无空行。每组数据以两个正整数 $N, M$ 开始,接下来 $N$ 行,每行 $M$ 个用空格隔开的整数,意义如题所述。
输出格式
对于每组数据输出一行。如果有解,则输出 $N$ 个整数,依次表示每一行取的数是多少。(这应该是一个 $1$ 到 $N$ 的排列)如果无解,则输出任意卖萌表情。
样例一
input
2 5 10 0 1 0 2 3 0 0 4 0 5 2 0 3 0 0 1 0 5 4 0 4 2 1 0 0 0 3 0 5 0 0 3 0 4 0 5 0 1 2 0 1 0 0 3 2 4 5 0 0 0 5 10 0 1 0 2 3 0 0 4 0 5 2 0 3 0 0 1 0 5 4 0 4 2 1 0 0 0 3 0 5 0 0 3 0 4 0 5 0 1 2 0 1 0 0 3 2 4 5 0 0 0
output
4 5 3 1 2 5 4 3 1 2
explanation
两组输入数据是相同的。由于结果不唯一,你可以给出任意一组合法答案。
限制与约定
对于 20% 的数据,$M < 8, T < 8$。
对于 40% 的数据,$N < 8, T < 8$。
对于 100% 的数据,$N < 200, M < 400, T < 50$。
卖萌表情包括但不限于“\(^o^)/” (不含引号).
由于输入数据较大, 请自行优化输入方法.