Ma trận

Cho một ma trận vuông A kích thước $N * N$, ban đầu tất cả các phần tử đều bằng 0. Bạn muốn biến đổi ma trận này thành ma trận B cũng có kích thước $N * N$. Bạn được phép thực hiện thao tác sau:

• Chọn một hoán vị P kích thước N.
• Chọn một số nguyên dương X bất kỳ.
• Với mỗi i ($1 \le i \le N$), cộng X vào $A_{i, P_i}$.

Một hoán vị kích thước N được định nghĩa là một dãy các số nguyên dương có giá trị từ 1 đến N, trong đó không có hai phần tử nào có cùng giá trị.

Bạn được cho ma trận B. Bạn được phép thực hiện tối đa 2500 thao tác. Hãy xác định xem bạn có thể biến đổi ma trận A thành ma trận B hay không? Nếu có thể, hãy chỉ ra một phương án thực hiện.

Đầu vào:

• Dòng đầu tiên chứa số nguyên T là số lượng test case.
• Dòng đầu tiên của mỗi test case chứa số nguyên N là kích thước của ma trận.
• Trong N dòng tiếp theo, dòng thứ i chứa N số nguyên lần lượt là các phần tử trên dòng thứ i của ma trận B.

Giới hạn:

• $1 \le T \le 5$
• $1 \le N \le 50$
• $0 \le B_{i, j} \le 10^9$

Dữ liệu đảm bảo trong ma trận B có ít nhất một phần tử lớn hơn 0.

Đầu ra: Với mỗi test case:

• Nếu không có cách nào để tạo ra chính xác ma trận B, in ra một số duy nhất là -1.
• Nếu có cách thực hiện, đầu tiên in ra số nguyên K ($0 \le K \le 2500$) là số lượng thao tác. Trong $K$ dòng tiếp theo, mỗi dòng in ra $N+1$ số nguyên dương mô tả các thao tác theo thứ tự như sau:
  • Số nguyên dương đầu tiên là giá trị X của thao tác ($1 \le X \le 10^9$).
  • N số nguyên dương tiếp theo lần lượt mô tả hoán vị P.

Nếu có nhiều phương án thỏa mãn, bạn có thể in ra phương án bất kỳ.

Ví dụ 1:

Đầu vào:

3
4
1 1 1 1
0 2 0 2
2 0 1 1
1 1 2 0
3
1 2 3
4 5 6
7 8 9
1
314159

Đầu ra:

4
1 2 4 3 1
1 3 4 1 2
1 4 2 1 3
1 1 2 4 3
-1
1
314159 1