QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 512 MB Total points: 100
[+2]

# 11. 矩阵变换

Statistics

给出一个 NM 列的矩阵A, 保证满足以下性质:

  1. M>N
  2. 矩阵中每个数都是 [0,N] 中的自然数。
  3. 每行中, [1,N] 中每个自然数都恰好出现一次。这意味着每行中 0 恰好出现 MN 次。
  4. 每列中,[1,N] 中每个自然数至多出现一次。

现在我们要在每行中选取一个非零数,并把这个数之后的数赋值为这个数。我们希望保持上面的性质4,即每列中,[1,N] 中每个自然数仍然至多出现一次。

输入格式

第一行一个正整数 T,表示数据组数。

后面包含 T 组数据,各组数据之间无空行。每组数据以两个正整数 N,M 开始,接下来 N 行,每行 M 个用空格隔开的整数,意义如题所述。

输出格式

对于每组数据输出一行。如果有解,则输出 N 个整数,依次表示每一行取的数是多少。(这应该是一个 1N 的排列)如果无解,则输出任意卖萌表情。

样例一

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^)/” (不含引号).

由于输入数据较大, 请自行优化输入方法.