hugo_daovang2

//Hugo_daovang2: neu khong dao duoc tat ca thi in ra -1
#include <iostream>
using namespace std;

int N, G;
int gold[5][3];
int map[21][21], visited[21][21];
int ans, x_min, y_min, maxCnt;
int front, rear;
int dx[4] = {-1,0,1,0};
int dy[4] = {0,-1,0,1};

struct Node{
	int r, c;
};

Node queue[10000];
void en(int x, int y){
	Node node;
	node.r = x;
	node.c = y;
	rear++;
	queue[rear] = node;
}

Node de(){
	front++;
	return queue[front];
}

void reset(){
	for(int i = 0; i < N; i++){
		for(int j = 0; j < N; j++){
			visited[i][j] = 0;
		}
	}
	for(int j = 0; j < G; j++){
		gold[j][2] = 0;
	}
}

bool check(){
	for(int i = 0; i < G; i++){
		if(visited[gold[i][0]][gold[i][1]] == 0) return true;
	}
	return false;
}

void BFS(int x, int y){
	reset();
	front = rear = -1;
	en(x,y);
	visited[x][y] = 1;
	while(front != rear){
		Node node = de();
		for(int k = 0; k < 4; k++){
			int nx = node.r + dx[k];
			int ny = node.c + dy[k];
			if(nx >= 0 && nx < N && ny >= 0 && ny < N){
				if(visited[nx][ny] == 0){
					if(map[nx][ny] != 0){
						en(nx, ny);
						visited[nx][ny] = visited[node.r][node.c] + 1;
					}
				}
			}
		}
	}
}

void solve(){
	for(int i = 0; i < N; i++){
		for(int j = 0; j < N;  j++){
			if(map[i][j] == 1){
				BFS(i,j); // bfs tu diem dat trai den het mang
				int maxx = 0;
				int cnt = 0;
				for(int k = 0; k < G; k++){
					if(visited[gold[k][0]][gold[k][1]] != 0){
						maxx = (visited[gold[k][0]][gold[k][1]] - 1) > maxx ? (visited[gold[k][0]][gold[k][1]] - 1) : maxx;
						cnt++;
					}
				}
				if(maxx == 0) continue;
				if(maxCnt < cnt){
					maxCnt = cnt;
					ans = maxx;
					x_min = i;
					y_min = j;
				}
				if(maxCnt == cnt){
					if(ans > maxx){
						ans = maxx;
						x_min = i;
						y_min = j;
					}
				}
			}
		}
	}

}

int main(){
	//freopen("input.txt", "r", stdin);
	int t; 
	cin >> t;
	for(int tc = 0; tc < t; tc++){
		cin >> N >> G;
		for(int i = 0; i < G; i++){
			int r, c;
			cin >> r >> c;
			r--;
			c--;
			gold[i][0] = r;
			gold[i][1] = c;
			gold[i][2] = 0;
		}
		for(int i = 0; i < N; i++){
			for(int j = 0; j < N; j++){
				cin >> map[i][j];
				visited[i][j] = 0;
			}
		}
		for(int i = 0; i < G; i++){
			map[gold[i][0]][gold[i][1]] = 2;
		}
		ans = 10000;
		x_min = -1;
		y_min = -1;
		maxCnt = 0;
		BFS(gold[0][0],gold[0][1]);
		if(check())	ans = 10000;
		else{
			solve();
		}
		cout << "Case #" << tc+1 << endl;
		if(ans != 10000){
			cout << ans << endl;
		}
		else cout << "-1" << endl;

	}
	return 0;
}