#P3816. 矩阵变换

    ID: 3018 传统题 1000ms 512MiB 尝试: 906 已通过: 77 难度: 8 上传者: 标签>CF2400提高+/省选-二分图建模Gale–Shapley 稳定婚配算法2015年国家集训队测试

矩阵变换

题目描述

给出一个 nn 行 mm 列的矩阵 AA,保证满足以下性质:

  1. m>nm>n;
  2. 矩阵中每个数都是 [0,n][0,n] 中的自然数。
  3. 每行中,[1,n][1,n] 中每个自然数都恰好出现一次,这意味着每行中 00 恰好出现 m−nm-n 次;
  4. 每列中,[1,n][1,n] 中每个自然数至多出现一次。

现在我们要在每行中选取一个非零数,并把这个数之后的数赋值为这个数。

我们希望保持上面的性质 44,即每列中,[1,n][1,n] 中每个自然数仍然至多出现一次。

输入格式

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

后面包含 TT 组数据,各组数据之间无空行。

每组数据以一行两个正整数 n,mn,m 开始。

接下来 nn 行,每行 mm 个用空格隔开的整数,意义如题所述。

输出格式

对于每组数据输出一行。

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

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
4 5 3 1 2
5 4 3 1 2

样例解释

两组输入数据是相同的。由于结果不唯一,你可以给出任意一组合法答案。

数据规模与约定

对于 100%100\% 的数据,1≤n≤2001\leq n\leq 200,1≤m≤4001\leq m\leq 400,1≤T≤501\leq T\leq 50。

卖萌表情包括但不限于 (\^o^)/。

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

请不要提交,期待SPJ。

来源

20152015 年国家集训队测试。