题目描述

你有一张 $n \times m$ 的方格纸，其中一些格子被涂上了颜色。把所有涂色格子的集合记作 $A$。集合 $A$ 是连通的。你的任务是求出最少要从 $A$ 中删去多少个格子，才能使它不再连通。

称一个涂色格子集合是连通的，当且仅当对该集合中任意两个格子 $a$ 和 $b$，都存在一个由集合中格子构成的序列，以 $a$ 开头、以 $b$ 结尾，且序列中除最后一个格子外，每个格子都与下一个格子共享一条边。空集和只含一个格子的集合按定义视为连通。

输入格式

输入的第一行包含两个用空格隔开的整数 $n$ 和 $m$（$1 \le n, m \le 50$），表示纸张的尺寸。

接下来 $n$ 行每行 $m$ 个字符，描述这张方格纸：第 $i$ 行第 $j$ 个字符若为 "#"，表示对应格子被涂色（属于集合 $A$）；若为 "."，表示该格子未涂色（不属于 $A$）。保证所有涂色格子的集合 $A$ 连通且非空。

输出格式

第一行输出需要删除的最少格子数，使集合 $A$ 变得不连通。如果不可能做到，输出 -1。

5 4
####
#..#
#..#
#..#
####

2

5 5
#####
#...#
#####
#...#
#####

2

说明/提示

第一组样例中，可以删除任意两个不共边的格子，删除后涂色格子集合就不再连通。

第二组样例的说明如下图所示：左边是初始的格子集合，右边是删除格子后的集合，被删除的格子标了叉。