CF18E Flag 2

根据一项新的 ISO 标准，每个国家的国旗必须有一个奇特的棋盘格字段，大小为 $n \times m$，每个格子都要被完全涂成 26 种颜色中的一种。具体要求如下： - 每一行最多只能使用两种不同的颜色。 - 任何两个相邻的格子不能涂成相同的颜色。 请注意，在同一列中可以使用超过两种不同的颜色。 Berland 政府决定根据新标准调整本国国旗，但他们希望这些更改尽可能少。给定 Berland 国旗的描述，请你计算满足新 ISO 标准所需最少重涂的格子数量，并给出符合要求的国旗方案（只需输出一种即可）。

第一行包含两个整数 $n$ 和 $m$（$1 \leq n, m \leq 500$），分别表示国旗的行数和列数。接下来的 $n$ 行描述了国旗的初始状态，每行包含 $m$ 个字符，每个字符是小写字母 $a$ 到 $z$，表示对应格子的颜色。

第一行输出为满足新标准最少需要重涂的格子数。接下来输出 $n$ 行，每行 $m$ 个字符，表示修改后的国旗方案。你输出的方案必须是在原始国旗的基础上，经过最少次数的重涂得到的。如果有多种方案，输出任意一种即可。

由 ChatGPT 5 翻译