hugo_daovang1_c2

#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};

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(gold[i][2] == 1) return true;
	}
	return false;
}

struct Node{
	int r, c;
};

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

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

void BFS(int x, int y){
	reset();
	front = rear = -1;
	push(x,y);
	visited[x][y] = 1;
	while(front != rear){
		Node node = pop();
		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){
						push(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);
				int max = 0;
				int cnt = 0;
				for(int k = 0; k < G; k++){
					if(visited[gold[k][0]][gold[k][1]] != 0){
						max = (visited[gold[k][0]][gold[k][1]] - 1) > max ? (visited[gold[k][0]][gold[k][1]] - 1) : max;
						gold[k][2] = 1;
						cnt++;
					}
				}
				if(max == 0) continue;
				if(maxCnt < cnt){
					maxCnt = cnt;
					ans = 10000;
				}
				if(maxCnt == cnt){
					if(ans > max){
						ans = max;
						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;
		solve();
		reset();
		BFS(x_min, y_min);
		for(int k = 0; k < G; k++){
			if(visited[gold[k][0]][gold[k][1]] != 0){
				gold[k][2] = 1;
			}
		}
		cout << "Case #" << tc+1 << endl;
		if(ans != 10000){
			cout << ans << endl;
			for(int i = 0; i < G; i++){
				if(gold[i][2] == 0){
					cout << gold[i][0]+1 << " " << gold[i][1]+1 << endl;
				}
			}
		}
		else cout << "-1" << endl;
		
	}

	while(1){}
}