解开《贝尔兰词典》后,科学家们设法阅读了当时编年史家的笔记。例如,他们了解了古代贝兰德部落的首领是如何选出的。
一旦挑选了足够多的冒充者,就会在他们中间进行以下测试:部落的酋长拿一块由水平和垂直条纹划分成相同正方形的石板(石板由N行和M列组成),并将每个正方形涂成黑色或白色。然后,每个觊觎者都会得到一块同样大小但漆成白色的石板。一天之内,伪装者就可以给石板上任何侧面相连的方块涂上一些颜色。如果对于属于该集合的任何两个方格,存在一条属于该集合的路径,且该路径上的任何两个相邻方格共享一条边,则该集合称为链接的。每个冒充者的目标是以与酋长的石板完全相同的方式绘制他的石板。第一个画出这样的石板的人将成为新的酋长。
科学家发现了古代贝尔兰部落酋长所画的石板。如果新酋长必须按照给定的方式粉刷他的石板,请帮助他们确定找到新酋长所需的最少天数。
输入
第一行包含两个整数 N 和 M (1 ≤ N, M ≤ 50) — 板上的行数和列数。接下来的 N 行每行包含 M 个符号——板的最终颜色。 W 代表应涂成白色的正方形,B 代表应涂成黑色的正方形。
输出
在单行输出中,获得板所需着色所需的侧面链接区域的重新绘制次数最少。
示例
输入 #1
3 3 WBW BWB WBW
输出 #1
2
输入 #2
2 3 BBB BWB
输出 #2
1