CF1977D.XORificator

给定一个仅包含 $0$ 和 $1$ 的 $n \times m$ 二进制矩阵。你还拥有一个“异或器”，可以用它对选定的某一行进行翻转（即将该行的 $0$ 变为 $1$，$1$ 变为 $0$）。

如果某一列恰好包含一个 $1$，则称该列为“特殊列”。你的任务是，找出最多能同时让多少列成为特殊列，并给出应对哪些行使用异或器的方案。

每个测试点包含多个测试用例。输入的第一行为一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。接下来是每个测试用例的描述。

每个测试用例的第一行为两个整数 $n$ 和 $m$（$1 \leq n, m \leq 3 \times 10^5$，$n \cdot m \leq 3 \times 10^5$）。

接下来的 $n$ 行，每行包含一个长度为 $m$ 的二进制字符串，表示矩阵的一行。

保证所有测试用例中 $n \cdot m$ 的总和不超过 $3 \times 10^5$。

对于每个测试用例，输出两行。

第一行输出最多能同时成为特殊列的列数。

第二行输出一个长度为 $n$ 的二进制字符串，第 $i$ 个字符为 $0$ 表示不对第 $i$ 行使用异或器，为 $1$ 表示对第 $i$ 行使用异或器。

如果存在多种异或器使用方案都能达到最优答案，可以输出任意一种。

在第一个测试用例中，可以对第二行使用异或器，使得第 $2$、$3$、$4$ 列成为特殊列。

在第二个测试用例中，唯一的列已经是特殊列，因此无需使用异或器。

由 ChatGPT 4.1 翻译