India and China Origins

Accepts: 97
Submissions: 351
Time Limit: 2000/2000 MS (Java/Others)
Memory Limit: 65536/65536 K (Java/Others)
问题描述
很久以前,中国和印度之间并没有喜马拉雅山相隔,两国的文化交流很频繁。随着喜马拉雅山海拔逐渐增加,两个地区的交流也越来越少,最终没有了来往。




假设当时的地形和我画的一样,蓝色部分代表海洋,而且当时人们还没有发明轮船。黄色部分代表沙漠,而且沙漠上经常有野鬼散步,所以人们不敢到沙漠中行走。黑色的格子表示山峰,这些山峰都无比高大,所以人无法穿过。白色格子代表平原,人可以在平原上自由行走。人每次可以向相邻的四个格子走动。

此外,我们的考古学家发现还有一些山峰会逐渐形成,通过研究发现,位置在 $(x, y)$ (保证该位置之前没有山峰)的地方在 $i$ 年后出现了山峰。现在给你若干个位置出现山峰的时间,你可以计算出中国和印度之间的联系最早被彻底切断的时间吗?
输入描述
多组测试数据, 第一行为组数$T(T\leq 10)$。每组测试数据第一行包含两个数 $N, M (1 \leq N, M \leq 500)$, 表示地图的大小。接下来 $N$ 行长度为 $M$ 的 $01$ 字符串。$0$代表白色格子,$1$ 代表山峰。接下来有 $Q(1\leq Q \leq N\times M)$ 行,第 $i(1\leq i \leq Q)$ 两个整数 $(x,y),0 \leq x < N, 0 \leq y < M$ 表示在第 $i$ 年 $(x,y)$ 出现了一座山峰。
输出描述
对于每组测试数据,输出一个数, 表示两国最早失联的时间。如果最终两国之间还有联系则输出 $$-1$$。
输入样例
1
4 6
011010
000010
100001
001000
7
0 3
1 5
1 3
0 0
1 2
2 4
2 1
输出样例
4
Hint

从上图可以看到,两国在第四年彻底失去了联系。