Untitled

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#define MAX_SIZE 1000000
#define INF 10000000
using namespace std;
class Point{
public:
	int x;
	int y;
};
int Qx[MAX_SIZE], Qy[MAX_SIZE], front, rear;

void init(){
	front = rear = -1;
}

void push(int x, int y){
	rear++;
	Qx[rear] = x;
	Qy[rear] = y;
}

void pop(){
	front++;
}

int topX(){
	return Qx[front];
}

int topY(){
	return Qy[front];
}
bool isEmpty(){
	return front == rear;
}

int N, G;
int map[40][40] = {0};
Point postionGold[10] = {0};
int visited[100][100];
int vtHienTai[10] = {0};
int vtMin[10] = {0};
int minVt;
int numGold;
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

void reset(){
	for(int i = 0; i <= N; ++i){
		for(int j = 0; j <= N; ++j){
			visited[i][j] = INF;
		}
	}
	for(int i = 0; i < 10; ++i){
		vtHienTai[i] = -1;
	}
}

void BFS(int x, int y){
	reset();
	init();
	push(x, y);
	visited[x][y] = 0;
	bool ch = false;
	while (!isEmpty())
	{
		pop();
		int xx = topX();
		int yy = topY();
		for(int i = 0; i < 4; ++i){
			int gx = xx + dx[i];
			int gy = yy + dy[i];
			if(gx >= 1 && gx <= N && gy >= 1 && gy <= N){
				if(map[gx][gy] == 1 && visited[xx][yy] + 1 < visited[gx][gy]){
					push(gx, gy);
					visited[gx][gy] = visited[xx][yy] + 1;
				}
				else if(map[gx][gy] >= 2 && visited[xx][yy] + 1 < visited[gx][gy]){
					push(gx, gy);
					visited[gx][gy] = visited[xx][yy] + 1;
					vtHienTai[map[gx][gy]-1] = visited[xx][yy] + 1;
					ch = true;
				}
			}
		}
	}
	if(ch == true){
		int numgGoldHt = 0;
		int maxHt = 0;
		for(int i = 1; i <= G; i++){
			if(vtHienTai[i] != -1){
				numgGoldHt++;
				if(vtHienTai[i] > maxHt){
					maxHt = vtHienTai[i];
				}
			}
		}
		if(numgGoldHt > numGold){
			numGold = numgGoldHt;
			minVt = maxHt;
			/*cout << "1NumgoldHt: " << numgGoldHt << " " << numGold 
				<< "MaxHt: " << maxHt << " " << minVt <<endl;*/ 
			for(int i = 1; i <= G; i++){
				vtMin[i] = vtHienTai[i];
			}
		}
		else if(numgGoldHt == numGold){
			/*cout << "2NumgoldHt: " << numgGoldHt << " " << numGold 
				<< "MaxHt: " << maxHt << " " << minVt <<endl;*/ 
			if(maxHt < minVt){
				minVt = maxHt;
				for(int i = 1; i <= G; i++){
					vtMin[i] = vtHienTai[i];
				}
			}
		}
	}
}

int main(){
	//freopen("input.txt", "r", stdin);
	int T;
	cin >> T;
	for(int tc = 1; tc <= T; ++tc){
		cin >> N >> G;
		for(int i = 1; i <= G; ++i){
			vtMin[i] = -1;
			cin >> postionGold[i].x >> postionGold[i].y;
		}
		for(int i = 1; i <= N; ++i){
			for(int j = 1; j <= N; ++j){
				cin >> map[i][j];
			}
		}
		numGold = 0;
		minVt = INF;
		for(int i = 1; i <= G; ++i){
			map[postionGold[i].x][postionGold[i].y] = i+1;
		}
		for(int i = 1; i <= N; ++i){
			for(int j = 1; j <= N; ++j){
				if(map[i][j] != 0){
					BFS(i, j);
				}
			}
		}
		if(numGold == 0){
			cout << "Case #" << tc << endl << -1 << endl;
		}
		else if(numGold < G){
			cout << "Case #" << tc << endl << minVt << endl;
			for(int i = 1; i <= G; i++){
				if(vtMin[i] == -1){
					cout << postionGold[i].x << " " << postionGold[i].y << endl;
				}
			}
		}
		else if(numGold == G){
			cout << "Case #" << tc << endl << minVt << endl;
		}
	}

	return 0;
}