U214960 抓人游戏

预言家 大A 和 大B 在玩抓人游戏，大A 和 大B 每一个时间单位均移动一个单位，如果 大A 在某个单位时间与 大B 站在一起，那么 大A 就获胜，若T个时间单位后，大A 没获胜则 大B 获胜。但是 大A 是预言家，因此他够能够预判 大B 的行动轨迹。

大B 在一个边长为 $N$ 的正方形迷宫内，该迷宫有很多入口（迷宫边上没障碍物的地方即是入口），大A 可以从任何一个迷宫入口处进入迷宫。大A 想让你帮他算算，他最短可以在几个单位时间后获胜。 大A 把这个房间的地图用符号画了出来，他规定: - `.` 代表这个地方是没有障碍的。 - `*` 代表这个地方有障碍物，是不可走的。 - `A` 代表 大A 的初始位置。 - `B` 代表 大B 的初始位置。

第一行 $2$ 个整数，$N$ 和 $T$ ，空格隔开。 接下来的 $N$ 行，每行 $N$ 个字符，表示 大A 画的地图。 接下来的 $T$ 行，每行 $2$ 个整数，$x,y$，表示 大B 在第 $_i$ 个时间单位的位置。

第一行一个整数 $K$ ，表示 大A 最短可以在过了 $K$ 个单位时间后 获胜，如果他不可以在 大B 胜利前获胜，那么请输出 $-1$。

样例解释#1： 大A 移动路径：3 1 -> 3 2 -> 2 2， 大B 移动路径：2 4 -> 2 3 -> 2 2， 因此最短时间为 2 。 **提示**：为了游戏的可玩性，所以他们规定 大A 走过的路不可再走。 对于所有数据 $5 ≤ N ≤ 100 , 1 ≤ T ≤ 100 , 1 ≤ M ≤ 10$