← 返回题目列表

Codeforces · 18/E

E. 标志 2

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

根据新的ISO标准,奇怪的是,每个国家的国旗都应该有一个n×m的方格区域,每个方格都应该涂上26种颜色中的一种。设置了以下限制:

- 每行最多可以使用两种不同的颜色。
- 两个相邻的方块不能涂成相同的颜色。

请注意,在一列中可以使用两种以上不同的颜色。

Berland 政府决定根据新标准对本国国旗进行更改,同时他们希望这些更改最小化。根据 Berland 旗帜的给定描述,您应该找出需要涂成不同颜色的最小方块数量,以使旗帜符合新的 ISO 标准。您也可以建造新伯兰国旗的可能变体之一。

输入

第一个输入行包含 2 个整数 n 和 m (1 ≤ n, m ≤ 500) — 分别是 Berland 标志中的行数和列数。接下来是标志的描述:接下来的 n 行每行包含 m 个字符。每个字符都是a到z的字母,代表对应方块的颜色。

输出

在第一行中输出需要重新绘制的最小方块数量,以使标志符合新的 ISO 标准。以下 n 行应包含新标志的可能变体之一。不要忘记,您提出的旗帜变体应该源自旧旗帜,并且重新绘制的方块数量最少。如果答案不唯一,则输出任何一个。

示例

输入 #1

3 4
aaaa
bbbb
cccc

输出 #1

6
abab
baba
acac

输入 #2

3 3
aba
aba
zzz

输出 #2

4
aba
bab
zbz