給你一個 M*N 的地圖，上面標記井字號的地方是陸地，其他地方是海洋。目前所有的陸地形成了連通的一塊(這裡的連通指的是四方向的連通，也就說任兩格可以以上下左右若干次之後互相走得到。
請問至少要將幾個格子的陸地變成海洋，使得陸地被分成恰好兩個連通塊？
一個輸入檔包含多筆測試資料，第一行包含測資筆數 T (T<=100)。
對於每一筆測試資料，第一列有兩個正整數 M, N，接下來有 M 行，每行有一個長度為 N 的字串。
至少佔 20% 分數的測試資料滿足：M, N<=10。
至少佔 80% 分數的測試資料滿足：M, N<=50。
至少佔 100% 分數的測試資料滿足：M, N<=1000。
輸入保證陸地是連通的，至少有一格是陸地。
對於每一筆測試資料請輸出要變海洋的格子數，若任何方法都不能讓陸地被分成恰好兩個連通塊，請輸出 -1。
2 5 5 ##### #...# ##### #...# ##### 5 6 ...... ...... ..#... ...... ......
2 -1
Migrated from old NTUJ.
CF193A
| No. | Testdata Range | Score |
|---|