D - Dungeon Master

縦 マス，横 マスの マスからなるグリッドで表されるダンジョンがあります．
上から 行目，左から 列目のマス は， が # のとき壁であり，. のとき道です．

このダンジョンの主である MojaMoja 君は，次の条件を満たすように， 組の マスを結ぶワープホールを非負整数個設置します．

条件

• 任意の道のマスにいる人が， 回以上の移動を繰り返すことによって，任意の道のマスへ到達することができる．

ここで，ある道のマス にいる人が，ある道のマス へ移動できるとき， マス は以下の条件のうち つ以上を満たします．

• とするとき，
• 組の マス または を結ぶワープホールが存在する

MojaMoja 君が条件を満たすために，最小で何組のワープホールを設置する必要があるか，求めてください．

• は . か # のうちのいずれか

入力は以下の形式で標準入力から与えられる．

答えを出力せよ．

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

2

たとえば，道のマスの組 を結ぶワープホールと， を結ぶワープホールとを設置することで条件を満たします．
つ未満のワープホールによって目標を達成することはできないため，2 を出力します．

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

2

2 4
#.#.
.#.#

3