← 返回题目列表

Codeforces · 426/B

B. Sereja 和镜像

中文机器翻译题面 查看原题

假设给定一个大小为 x × y 的矩阵 b,让我们确定镜像矩阵 b 的操作。矩阵 b 的镜像是一个 2x × y 矩阵 c,它具有以下属性:

- 矩阵 c 的上半部分(数字从 1 到 x 的行)与 b 完全匹配;
- 矩阵 c 的下半部分(行数从 x + 1 到 2x)与上半部分对称;对称线是分隔两半的线(位于 x 行和 x + 1 行之间的中间线)。

Sereja 有一个 n × m 矩阵 a。他想要找到这样的矩阵 b,如果我们对其执行多次(可能为零)镜像,则可以将其转换为矩阵 a。该矩阵最少可以包含多少行?

输入

第一行包含两个整数 n 和 m (1 ≤ n, m ≤ 100)。接下来的 n 行中的每一行都包含 m 个整数——矩阵 a 的元素。第 i 行包含整数 ai1、ai2、...、aim (0 ≤ aij ≤ 1) — 矩阵 a 的第 i 行。

输出

在单行中,打印问题的答案 — 矩阵 b 的最小行数。

示例

输入 #1

4 3
0 0 1
1 1 0
1 1 0
0 0 1

输出 #1

2

输入 #2

3 3
0 0 0
0 0 0
0 0 0

输出 #2

3

输入 #3

8 1
0
1
1
0
0
1
1
0

输出 #3

2

注意

在第一个测试样本中,答案是 2 × 3 矩阵 b:

如果我们对此矩阵执行镜像操作,我们将得到输入中给出的矩阵 a: