#1737. Matrix

    ID: 1737 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest1086来源:qoj.ac数据:公开样例数学

Matrix

Matrix

题目描述

标题: Matrix - Problem - QOJ.ac

Statistics

The problem was used in the following contests:

小 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。

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 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 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
-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