小 T 特别喜欢矩阵,尤其是置换矩阵,即每行每列恰有一个 1,其余位置为 0 的矩阵。现在她的面前有一个 N×N 的整数矩阵 A。她想知道,是否存在一组置换矩阵 B1,B2,⋯,Bm(∀i≠j,Bi≠Bj),对于这一组置换矩阵,有且仅有一组非负整系数 α1,α2,⋯,αm,使得 A=α1B1+α2B2+⋯+αmBm
并且由于小 T 不喜欢过于复杂的解,在有解的情况下,她希望你给的解中置换矩阵的种类不能过多。具体地,倘若有解,她接受 m≤N2 的任意一组解。
输入格式
第一行,一个整数 T,表示数据组数。
对于每一组数据,第一行一个整数 N,接下来 N 行,每行 N 个整数表示矩阵 A 中对应位置的元素。数据保证 A 不为零矩阵。
输出格式
对于每组数据,如果不存在解,则输出一行 “-1”(不包含引号);否则,先输出一行一个整数 m,接下来 m 行,每行 N+1 个整数,其中第 i 行第一个整数为 αi,第 j>1 个整数为 Bi 中第 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≤N≤5。
- Subtask 2 (30 pts): 1≤N≤30。
- Subtask 3 (40 pts): 1≤N≤50。
对于 100% 的数据,1≤T≤10,−2×107≤Ai≤2×107。