题目背景

小邦妮来到越南下龙湾度假。海湾中散布着数以千计的石灰岩岛屿，岛与岛之间由形状复杂的海域分隔，有些小岛甚至被更大的环形岛屿包围。

邦妮希望恰好游览每座岛屿一次。由于不同岛屿之间未必能够直接乘船通行，她可能需要把全部岛屿分成若干条游览路线。请帮助她求出所需路线数量的最小值。

题目描述

给定一张大小为 $H\times W$ 的地图。地图中的每个格子为：

• x：陆地；
• .：海水。

两个格子只要有一个公共点就视为相邻。因此，一个格子最多与周围 $8$ 个格子相邻。

一座岛屿定义为一个极大的、由 x 格子组成的连通块，其中连通关系采用上述八方向相邻规则。

对于两座不同的岛屿，如果存在一个由 . 格子组成的连通块，并且这个连通块中：

• 至少有一个海水格子与第一座岛屿中的某个陆地格子相邻；
• 至少有一个海水格子与第二座岛屿中的某个陆地格子相邻；

那么称这两座岛屿之间存在一次海上通行。

一条游览路线是一个岛屿序列，序列中每对相邻岛屿之间都必须存在海上通行。

你需要把地图中的所有岛屿划分到若干条游览路线中，使得：

1. 每座岛屿恰好出现一次；
2. 每条路线中相邻的两座岛屿之间都存在海上通行；
3. 路线数量尽可能少。

请输出最少需要的游览路线数量。

输入格式

第一行包含两个整数 $H,W$，分别表示地图的行数和列数。

接下来 $H$ 行，每行包含一个长度为 $W$ 的字符串，描述地图。

输出格式

输出一行一个整数，表示游览所有岛屿所需的最少路线数量。

数据范围

• $1\le H,W\le 50$；
• 地图只包含字符 . 和 x；
• 地图中至少存在一座岛屿。

补充说明

• 一条游览路线可以只包含一座岛屿；
• 邦尼不能离开给定地图的范围；
• 题目假设邦妮可以通过其他方式从一条路线的终点前往下一条路线的起点，因此不同路线之间的转移不计入答案；
• 岛屿可能嵌套在其他岛屿内部。

样例 1

输入

4 11
..x..x..x..
..x..x..x..
..x..x..x..
..x..x..x..

输出

1

说明

最左侧、中间和最右侧三座岛屿可以依次组成一条游览路线，因此答案为 $1$。

样例 2

输入

9 11
x....x....x
.....x.....
.....x.....
.....x.....
xxxxxxxxxxx
.....x.....
.....x.....
.....x.....
x....x....x

输出

3

说明

五座岛屿至少需要分成三条游览路线。例如，可以让左上角小岛、十字形大岛和右上角小岛组成一条路线，另外两座小岛各自组成一条路线。

样例 3

输入

9 11
x....x....x
.....x.....
.....x.....
....x.x....
xxxx...xxxx
....x.x....
.....x.....
.....x.....
x....x....x

输出

1

说明

任意两座岛屿之间都存在海上通路，因此五座岛屿可以排在同一条游览路线中。

样例 4

输入

16 30
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
x............................x
x..xxxxxxxxxx....xxxxxxxxxx..x
x..x........x....x........x..x
x..x..xxxx..x....x.xxxxxx.x..x
x..x........x....x.x....x.x..x
x..xxxxxxxxxx....x.x.x..x.x..x
x................x.x....x.x..x
x................x.xxxxxx.x..x
x..xxxxxxxxxx....x........x..x
x..x........x....x........x..x
x..x..xxxx..x....x.xxxxxx.x..x
x..x........x....x........x..x
x..xxxxxxxxxx....xxxxxxxxxx..x
x............................x
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

输出

2

说明

岛屿可以嵌套在另一座岛屿内部。本例最少需要两条游览路线。

样例 5

输入

15 21
..........x..........
xxxxxxxxxxxxxxxxxxxxx
..........x..........
..........x.xxxxxxx..
..........x.x.....x..
..........x.x.x.x.x..
..........x.x.....x..
..........x.xxxxxxx..
..........x..........
..........x.xxxxxxx..
..........x.x.....x..
..........x.x.x.x.x..
..........x.x.....x..
..........x.xxxxxxx..
..........x..........

输出

1

说明

最少只需要一条游览路线。

样例 6

输入

15 21
..........x..........
xxxxxxxxxxxxxxxxxxxxx
..........x..........
..........x.xxxxxxx..
..........x.x.....x..
..........x.x.x.x.x..
..........x.x.....x..
..........x.xxxxxxx..
x.........x..........
..........x.xxxxxxx..
..........x.x.....x..
..........x.x.x.x.x..
..........x.x.....x..
..........x.xxxxxxx..
..........x..........

输出

2

说明

最少需要两条游览路线。

样例 7

输入

16 21
x.........x.........x
..........x..........
xxxxxxxxxxxxxxxxxxxxx
..........x..........
..........x.xxxxxxx..
..........x.x.....x..
..........x.x.x.x.x..
..........x.x.....x..
..........x.xxxxxxx..
x.........x.........x
..........x.xxxxxxx..
..........x.x.....x..
..........x.x.x.x.x..
..........x.x.....x..
..........x.xxxxxxx..
..........x.........x

输出

3

说明

最少需要三条游览路线。