题目背景

题目传送门 U511007 地刺大战僵尸

由于王の冻在课堂上说自己得了NOI金牌，赵老尸非常愤怒，于是决定从教室门发起肘击，肘飞所有课桌，然后拿走王の冻的金牌。王の冻不想失去自己的金牌，于是决定发起金牌保卫战。

也试试这些题目

• STJX0002 王之栋的魔法
• U580277 别样的进步大战
• U609367 二等分的NOI金牌

题目描述

王の冻的教室是一个 $n$ 行 $m$ 列的网格图，初始时上面种植有了一些学生用来抵挡赵老尸的肘击，学生都是小蒟蒻，写的入门题全WA，所以赵老师走到学生上看到学生写的代码就会被气死。

赵老尸会从王の冻的教室的右侧肘击：赵老尸可以选择第 $m$ 列的任意一个格子出发，它们可以移动到和当前格子有公共边的相邻课桌上去。它们想找到一条没有学生的路径到达教室的最左侧，即只要它们到达了第 $1$ 列，王の冻的NOI金牌就会被赵老尸给吃掉。

王の冻可以在网格图上补充学生。但是，种植学生的格子之间不能有公共边（不能相邻），这会使学生讲悄悄话。现在王の冻想知道他最少种多少个学生才能抵挡住赵老尸的肘击，如果王の冻找不到种植学生来抵挡赵老尸的方法，输出 $-1$。

输入格式

第一行一个整数 $T$ 表示输入数据的组数。

接下来 $T$ 组数据，每组数据的第一行两个整数 $n,m$ 表示王之栋教室的行数和列数。

接下来 $n$ 行，每行一个长为 $m$ 的字符串，用来表示这一行的学生种植情况，其中 "." 表示这里是空地，"#" 表示这里种植了一个学生。

输出格式

输出 $T$ 行，每行一个整数，表示在该组输入下如果王の冻不能保住他的NOI金牌（失败），输出 $-1$，否则输出王の冻最少需要种植的学生数量，使得种植完这些学生之后，赵老尸们找不到一条从最右侧到最左侧的路径。

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

0
-1
1

3
4 2
..
.#
#.
..
3 3
..#
#..
..#
5 5
.....
.....
.....
.....
.....

2
-1
5

说明/提示

【数据范围】

• 对于 $100\%$ 的数据，$1 \le T \le 10,1 \le n,m \le 1000$，初始的教室中不会有学生在相邻格子上，字符仅包含 . 和 # 两种字符

【cinbarhuchの威胁】

• 你小子最好不要让我知道你过不了第10个点

欲知后事如何，请见 STJX0002 王之栋的魔法

本题洛谷同步上传。U578817 赵老尸大战王之栋（赵老尸大战王の冻）