蜘蛛侠诺亚和魔方

时间限制：1 秒
内存限制：256 MB
输入：标准输入
输出：标准输出

题目描述

让我们暂时脱离故事的第二部分，回顾一下第一部分。蜘蛛侠诺亚对魔方非常感兴趣，决定不惜一切代价揭开这个神秘物体的所有秘密。但问题在于——他至今仍无法弄清楚这个奇怪的装置是什么，以及它的用途。

因此，他决定在黑白版本的魔方上进行练习，而且还是二维的，而不是三维的。为此，他取了一个大小为 $n \times m$ 的棋盘格，每个格子被涂成黑色或白色。与魔方类似，可以改变格子的颜色，但不能旋转，而是可以对表格执行两种操作之一：

最终目标是：使得存在一条从表格左上角到右下角的“全黑格子路径”，每一步只能向右或向下移动。换句话说，存在一个黑色格子序列 $(r_1, c_1), (r_2, c_2), \ldots, (r_{n+m-1}, c_{n+m-1})$，满足：

$(r_1, c_1) = (1, 1)$，即左上角格子；
$(r_{n+m-1}, c_{n+m-1}) = (n, m)$，即右下角格子；
对于序列中任意相邻的两个格子 $(r_i, c_i)$ 和 $(r_{i+1}, c_{i+1})$，要么 $r_i = r_{i+1}$ 且 $c_{i+1} = c_i + 1$，要么 $c_i = c_{i+1}$ 且 $r_{i+1} = r_i + 1$。

请计算得到这样一条路径所需的最少操作次数，或者报告无法通过翻转行和列得到这样的全黑格子路径。蜘蛛侠诺亚非常期待你的帮助。

第一行包含两个整数 $n$ 和 $m$（$1 \le n, m \le 2000$）——棋盘的高度和宽度。

接下来 $n$ 行，每行包含 $m$ 个字符，每个字符为 0 或 1，表示第 $i$ 行各格子的颜色。字符 0 表示白色，1 表示黑色。

如果不可能通过翻转行和列得到从左上角到右下角的全黑格子路径，则输出一个整数 $-1$。

否则，第一行输出两个整数 $r$ 和 $c$——需要翻转的行数和列数。第二行输出 $r$ 个整数，表示需要翻转的行的编号；第三行输出 $c$ 个整数，表示需要翻转的列的编号。

行和列的编号从 $1$ 开始（行从上到下，列从左到右）。可以按任意顺序输出行号和列号。在最小化 $r + c$ 的所有答案中，输出任意一个即可。

输入：

2 2
10
01

输出：

1 1
1 
1

输入：

输出：

1 0
4

输入：

输出：

2 1
2 1 
1