Little Prince and the Garden of Roses

题目描述

小王子站在一座盛开着玫瑰的花园前。

“早上好。”玫瑰们说道。

小王子注视着她们。她们看起来都和他的那朵花一模一样。

“你们是谁？”他震惊地问道。

“我们是玫瑰。”玫瑰们回答。

于是，小王子陷入了悲伤。他的花曾告诉他，她是整个宇宙中独一无二的玫瑰；然而现在，这里竟然有成千上万朵一模一样的玫瑰，聚集在同一座花园里。

假设这座玫瑰花园由 $n$ 行 $n$ 列组成，共有 $n^2$ 朵玫瑰。第 $i$ 行第 $j$ 列的玫瑰花瓣颜色为 $c_{i,j}$。

当小王子在花园中散步时，如果他发现同一行或同一列中有两朵玫瑰的花瓣颜色相同，他就会想起自己的玫瑰并非独一无二，从而伤心落泪。

幸运的是，你比小王子更早到达花园。你有一支神奇的画笔，可以为某些玫瑰的花茎涂上不同的颜色。所有花茎最初都是绿色，视为颜色 $0$。

你需要给部分玫瑰的花茎染色，使得：

• 对于任意位于同一行或同一列的两朵玫瑰；
• 它们不能同时拥有相同的花瓣颜色和相同的花茎颜色。

换句话说，如果两朵位于同一行或同一列的玫瑰花瓣颜色相同，那么它们的花茎颜色必须不同。

不同颜色的颜料准备起来十分耗时，因此你希望使用的颜料种类数尽可能少。请输出任意一种使用最少颜料种类的合法染色方案。

输入格式

第一行包含一个整数 $T$，表示测试用例数量。

对于每组测试用例：

• 第一行包含一个整数 $n$，表示花园的边长；
• 接下来 $n$ 行，每行包含 $n$ 个整数，其中第 $i$ 行第 $j$ 个整数为 $c_{i,j}$，表示第 $i$ 行第 $j$ 列玫瑰的花瓣颜色。

输出格式

对于每组测试用例：

第一行输出两个整数 $d,m$：

• $d$ 表示使用的不同颜料颜色数量；
• $m$ 表示被染色的玫瑰数量。

接下来输出 $m$ 行，每行三个整数 $i,j,c$，表示将第 $i$ 行第 $j$ 列玫瑰的花茎染成颜色 $c$。

未在输出中出现的玫瑰，其花茎颜色视为 $0$。

只要使用的颜料种类数 $d$ 最少，任何满足条件的方案均可接受。

数据范围

并保证：

• 至多有 $10$ 组测试数据满足 $n>20$；
• 至多有 $4$ 组测试数据满足 $n>100$。

输出中的整数需满足：

当 $d>0$ 时，每个染色操作满足：

样例

输入

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

输出

2 6
1 2 2
1 3 1
2 1 1
2 3 2
3 1 2
3 2 1
1 4
1 3 1
3 1 1
2 3 1
3 2 1
0 0

样例说明

样例输出仅为一种合法方案。

在第三组测试中，每朵玫瑰的花瓣颜色均不同，因此无需给任何花茎染色，输出 0 0。