P10554 [ICPC 2024 Xi'an I] Turn Off The Lights

Kitty 有 $n^2$ 个灯泡，这些灯泡组成了一个 $n\times n$ 的矩阵。 有一天，Kitty 发现这些灯泡中有些是亮的，有些是灭的。Kitty 想要把它们全部关闭。 为了实现她的目标，Kitty 可以执行三种类型的操作： - (1) 选择一行，反转这一行的状态。这意味着如果这一行的灯泡是亮的，经过此操作后，它将变为灭的。如果这一行的灯泡是灭的，经过此操作后，它将变为亮的。 - (2) 选择一列，反转这一列的状态。这意味着如果这一列的灯泡是亮的，经过此操作后，它将变为灭的。如果这一列的灯泡是灭的，经过此操作后，它将变为亮的。 - (3) 选择一个灯泡，反转这个灯泡的状态。**这种操作最多只能执行 $k$ 次。** 对于当前状态，帮助 Kitty 在 $3n$ 次操作内实现她的目标。

第一行包含两个整数 $n(1\leq n\leq 1000),k(0\leq k < n)$，如上所述。 接下来有 $n$ 行，每行有正好 $n$ 个数字，$0$ 表示此时灯泡是灭的，而 $1$ 表示相反。 输入中第 $(x+1)$ 行的第 $y$ 个数字表示坐标 $(x,y)$ 处的灯泡。

如果 Kitty 无法实现她的目标，输出 $-1$ 在一行中。 否则，第一行输出 $M(0\leq M\leq 3n)$，表示她需要执行的操作次数。 接下来的 $M$ 行中，每行包含 $2$ 个整数 $x,y$，用空格分隔。 如果 $1\leq x\leq n,1\leq y\leq n$，表示 Kitty 将反转坐标 $(x,y)$ 处的灯泡。 如果 $x=0,1\leq y\leq n$，表示 Kitty 将反转所有坐标为 $(z,y)1\leq z\leq n$ 的灯泡。 如果 $1\leq x\leq n,y=0$，表示 Kitty 将反转所有坐标为 $(x,z)1\leq z\leq n$ 的灯泡。 如果有多个答案，输出其中任意一个。

（由 ChatGPT 4o 翻译）