题目描述

对于由非负整数组成的集合 $X$，我们定义 $f(X)$ 为：所有可以表示为 $X$ 中两个整数（可以是相同的整数）按位异或（$\mathrm{XOR}$）得到的非负整数组成的集合。例如，当 $X=\lbrace 1,\ 2,\ 4\rbrace$ 时，$f(X)=\lbrace 0,\ 3,\ 5,\ 6\rbrace$。

给定一个包含 $N$ 个小于 $2^M$ 的非负整数组成的集合 $S=\lbrace A_1,\ A_2,\ \dots,\ A_N\rbrace$。

你可以进行如下操作任意次：

• 将 $S$ 分成两个集合 $T_1$ 和 $T_2$（允许 $T_1$ 或 $T_2$ 为空集）。然后，用 $f(T_1)$ 与 $f(T_2)$ 的并集替换 $S$。

请你求出将 $S$ 变为 $\lbrace 0\rbrace$ 所需的最小操作次数。

按位异或（$\mathrm{XOR}$）运算的定义如下：对于非负整数 $A$、$B$，$A\oplus B$ 的二进制表示中，每一位 $2^k$（$k\geq 0$）上的数，如果 $A$ 和 $B$ 在该位上只有一个为 $1$，则该位为 $1$，否则为 $0$。

例如，$3\oplus 5=6$（二进制表示为 $011\oplus 101=110$）。 一般地，$k$ 个非负整数 $p_1,p_2,p_3,\dots,p_k$ 的按位异或定义为 $(\dots((p\_1\oplus p\_2)\oplus p\_3)\oplus\dots\oplus p\_k)$，并且可以证明其结果与顺序无关。

输入格式

输入通过标准输入给出，格式如下：

$N$ $M$
$A_1$
$A_2$
$\vdots$
$A_N$

输出格式

请输出答案。

样例 1

输入

4 2
00
01
10
11

输出

2

样例 2

输入

1 8
10011011

输出

1

样例 3

输入

1 2
00

输出

0

样例 4

输入

20 20
10011011111101101111
10100111100001111100
10100111100110001111
10011011100011011111
11001000001110011010
10100111111011000101
11110100001001110010
10011011100010111001
11110100001000011010
01010011101011010011
11110100010000111100
01010011101101101111
10011011100010110111
01101111101110001110
00111100000101111010
01010011101111010100
10011011100010110100
01010011110010010011
10100111111111000001
10100111111000010101

输出

10

说明/提示

限制条件

• $1\leq N\leq 300$
• $1\leq M\leq 300$
• $0\leq A_i<2^M$
• $A_i\ (1\leq i\leq N)$ 互不相同
• 每个 $A_i$ 都以恰好 $M$ 位的二进制形式给出（如果 $A_i$ 的二进制位数不足 $M$，则会补前导零）
• 所有输入均为整数

样例解释 1

第一次操作时，将 $T_1=\lbrace 0,1\rbrace$，$T_2=\lbrace 2,3\rbrace$，则 $f(T_1)=\lbrace 0,1\rbrace$，$f(T_2)=\lbrace 0,1\rbrace$，因此 $S$ 被替换为 $\lbrace 0,1\rbrace$。第二次操作时，将 $T_1=\lbrace 0\rbrace$，$T_2=\lbrace 1\rbrace$，则 $S=\lbrace 0\rbrace$。无法在少于 $2$ 次操作内将 $S$ 变为 $\lbrace 0\rbrace$，所以答案为 $2$。

样例解释 2

第一次操作时，将 $T_1=\lbrace 155\rbrace$，$T_2=\lbrace\rbrace$，则 $S$ 变为 $\lbrace 0\rbrace$。操作时允许 $T_1$ 或 $T_2$ 为空集。

样例解释 3

初始时 $S=\lbrace 0\rbrace$，无需进行任何操作。

由 ChatGPT 4.1 翻译