QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 256 MB Total points: 100
[+4]
统计

小 T 特别喜欢矩阵,尤其是置换矩阵,即每行每列恰有一个 1,其余位置为 0 的矩阵。现在她的面前有一个 N×N 的整数矩阵 A。她想知道,是否存在一组置换矩阵 B1,B2,,Bmij,BiBj),对于这一组置换矩阵,有且仅有一组非负整系数 α1,α2,,αm,使得 A=α1B1+α2B2++αmBm

并且由于小 T 不喜欢过于复杂的解,在有解的情况下,她希望你给的解中置换矩阵的种类不能过多。具体地,倘若有解,她接受 mN2 的任意一组解。

输入格式

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

对于每一组数据,第一行一个整数 N,接下来 N 行,每行 N 个整数表示矩阵 A 中对应位置的元素。数据保证 A 不为零矩阵。

输出格式

对于每组数据,如果不存在解,则输出一行 “-1”(不包含引号);否则,先输出一行一个整数 m,接下来 m 行,每行 N+1 个整数,其中第 i 行第一个整数为 αi,第 j>1 个整数为 Bi 中第 j1 行的 1 的列号。

样例数据

样例 1 输入

5
2
1 0
0 1
2
1 1
1 0
2
1 1
1 1
2
-1 0
0 -1
2
100 99
99 100

样例 1 输出

1
1 1 2
-1
2
1 1 2
1 2 1
-1
2
100 1 2
99 2 1

样例 2 输入

5
3
1 2 4
4 0 4
3 3 26962
3
4 0 -6
0 1 3
-3 0 -2
3
1 1 2
0 2 2
3 1 0
3
3 3 5
6 4 1
2 4 5
3
4 4 5
3 3 7
6 6 1

样例 2 输出

-1
-1
3
1 1 3 2
1 2 3 1
2 3 2 1
5
3 1 2 3
1 3 2 1
2 2 1 3
4 3 1 2
1 2 3 1
5
1 1 2 3
3 1 3 2
3 3 1 2
4 2 3 1
2 3 2 1

子任务

  • Subtask 1 (30 pts): 1N5
  • Subtask 2 (30 pts): 1N30
  • Subtask 3 (40 pts): 1N50

对于 100% 的数据,1T102×107Ai2×107