QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 256 MB Total points: 100

# 5371. Matrix

Statistics

小 T 特别喜欢矩阵,尤其是置换矩阵,即每行每列恰有一个 $1$,其余位置为 $0$ 的矩阵。现在她的面前有一个 $N \times N$ 的整数矩阵 $A$。她想知道,是否存在一组置换矩阵 $B_1, B_2, \cdots, B_m$($\forall i \ne j, B_i \ne B_j$),对于这一组置换矩阵,有且仅有一组非负整系数 $\alpha_1, \alpha_2, \cdots, \alpha_m$,使得 $A = \alpha_1B_1 + \alpha_2B_2 + \cdots + \alpha_m B_m$

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

输入格式

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

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

输出格式

对于每组数据,如果不存在解,则输出一行 “-1”(不包含引号);否则,先输出一行一个整数 $m$,接下来 $m$ 行,每行 $N+1$ 个整数,其中第 $i$ 行第一个整数为 $\alpha_i$,第 $j>1$ 个整数为 $B_i$ 中第 $j-1$ 行的 $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): $1 \leq N \leq 5$。
  • Subtask 2 (30 pts): $1 \leq N \leq 30$。
  • Subtask 3 (40 pts): $1 \leq N \leq 50$。

对于 $100\%$ 的数据,$1 \leq T \leq 10$,$-2 \times 10^7 \leq A_i \leq 2 \times 10^7$。