#include<iostream>
using namespace std;
int T, n, g;
int gold[105][2], arr[105][105], visit[105][105];
int dx[4] = {-1,0,1,0};
int dy[4] = {0,1,0,-1};
int r;
int kt1 = 0, kt2 = 0;
int rear, front;
struct toado{
int x, y;
};
toado queue[1000000];
void init(){
rear = 0;
front = 0;
}
void push(int x, int y){
queue[rear].x = x;
queue[rear].y = y;
rear++;
}
toado pop(){
toado t = queue[front];
front++;
return t;
}
void nhap(){
cin >> n >> g;
for(int i = 0; i < g; i ++) {
cin >> gold[i][0] >> gold[i][1];
gold[i][0] --;
gold[i][1] --;
}
for(int i = 0; i < n; i ++) {
for(int j = 0; j < n; j ++) {
arr[i][j] = 0;
}
}
for(int i = 0; i < n; i ++) {
for(int j = 0; j < n; j ++) {
cin >> arr[i][j];
}
}
}
void reset() {
for(int i = 0; i < n; i ++) {
for(int j = 0; j < n; j ++) {
visit[i][j] = 100000;
}
}
}
bool cdk(int x, int y) {
if(x >= 0 && x < n && y >= 0 && y < n) return true;
return false;
}
void BFS(int x, int y) {
init();
push(x,y);
visit[x][y] = 0;
while(front < rear) {
toado t = pop();
for(int i = 0; i < 4; i ++) {
int xx = t.x + dx[i];
int yy = t.y + dy[i];
if(cdk(xx,yy) && arr[xx][yy]) {
if(visit[xx][yy]==100000) {
push(xx,yy);
visit[xx][yy] = visit[t.x][t.y] + 1;
}
else if(visit[xx][yy] > visit[t.x][t.y] + 1) visit[xx][yy] = visit[t.x][t.y] + 1;
}
}
}
}
bool check(int x, int y) {
for(int i = 0; i < g; i ++) {
if(x == gold[i][0] && y == gold[i][1]) return false;
}
return true;
}
void in() {
kt1 = 0; kt2 = 0;
int sav = 0;
for(int i = 0; i < g; i ++) {
int x = gold[i][0];
int y = gold[i][1];
if(visit[x][y] == 100000) {
kt1 ++;
}
else {
kt2++;
if(visit[x][y] > sav) sav = visit[x][y];
}
}
if(kt2 == g) {
if(r > sav) r = sav;
}
}
int main() {
freopen("input.txt", "r", stdin);
cin >> T;
for(int tc = 1; tc <= T; tc++) {
nhap();
r = 100000;
for(int i = 0; i < n; i ++) {
for(int j = 0; j < n; j ++) {
if(check(i,j) && arr[i][j]) {
reset();
BFS(i,j);
in();
/*cout << r << endl;
for(int i = 0; i < n; i ++) {
for(int j = 0; j < n; j ++) {
cout << visit[i][j] << "\t";
}
cout << endl;
}
cout << endl << endl;*/
}
}
}
cout << "Case #" << tc << endl;
if(r == 100000) cout << -1 << endl;
else cout << r << endl;
}
return 0;
}
3
5 2
4 3
3 4
1 1 0 0 0
1 1 0 0 0
1 1 1 1 1
1 1 1 0 1
1 1 1 1 1
8 2
5 6
6 4
1 1 1 1 1 1 0 0
1 1 1 1 1 1 1 0
1 1 0 1 0 1 1 0
1 1 1 1 0 1 1 0
1 1 1 1 1 1 1 0
1 1 1 1 1 1 1 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
10 4
3 4
4 3
4 5
6 10
1 0 0 1 1 0 0 0 1 0
1 1 1 1 0 1 1 0 1 0
1 0 0 1 0 1 1 1 0 1
1 0 1 0 1 1 1 1 1 0
0 1 0 0 1 1 1 1 0 0
1 1 0 0 1 1 1 0 1 1
1 0 0 1 0 1 0 1 1 0
1 0 1 1 0 0 1 1 0 0
1 1 1 1 1 1 1 1 0 1
1 1 1 1 1 0 0 1 1 1
Case #1
1
Case #2
2
Case #11
1
4 3
4 5
6 10