题目背景

译自 COCI 2024/2025 #3 T3。$\texttt{1s,0.5G}$。满分为 $90$。

题目描述

有一个初始为全白的 $n\times n$ 矩阵。

每次操作可以选择一列 / 一行，将这一列 / 一行覆盖成红色 / 蓝色。

给定矩阵的目标状态，试构造一组操作序列使得矩阵达到目标状态，或者报告无解。

不需要最小化操作序列的长度，合法即可得分。

输入格式

第一行，一个正整数 $n$。

接下来 $n$ 行，每行 $n$ 个正整数，第 $i$ 行第 $j$ 个整数 $a_{i,j}$ 描述目标状态中第 $i$ 行第 $j$ 列格子的颜色：$0$ 表示白色，$1$ 表示红色，$2$ 表示蓝色。

输出格式

如果无解，输出 $-1$。

否则，第一行输出一个整数 $k$，表示操作序列长度。你需要保证 $0\le k\le 4\, 000$。

接下来 $k$ 行，每行三个正整数 $a,b,c$，依次描述操作：

• $a\in \{1,2\}$：$a=1$ 代表选择的是行，$a=2$ 代表选择的是列。
• $1\le b\le n$：代表选择的是第 $b$ 行（列）。
• $c\in \{1,2\}$：代表涂的是什么颜色。$1$ 表示红色，$2$ 表示蓝色。

3
0 0 1
1 1 1
0 0 1

2
2 3 1
1 2 1

3
1 1 2
2 1 1
2 1 1

-1

4
0 1 2 1
2 2 2 1
0 1 2 1
1 1 2 1

5
2 2 1
1 2 2
2 4 1
1 4 1
2 3 2

提示

对于 $100\%$ 的数据，保证 $1\le n\le 2\times 10^3$。

• 特殊性质 A：$a_{i,j}\in\{0,1\}$。