Untitled

#include <iostream>
using namespace std;

int n,g;
int map[21][21];
int visit_map[21][21];
int Qx[3000];
int Qy[3000];
int Qd[3000];
int gold[2][4];
int visit_gold[8];
int visit_gold_kq[8];
int r = -1, f = -1;
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
bool check;
void push(int x, int y, int d){
	r++;
	Qx[r] = x;
	Qy[r] = y;
	Qd[r] = d;
}
void pop(int &x, int &y, int &d){
	f++;
	x = Qx[f];
	y = Qy[f];
	d = Qd[f];
}
void reset_visit_gold(){
	for(int i = 2; i < g + 2; i++){
		visit_gold[i] = 0;
	}
}
void reset_visit_gold_kq(){
	for(int i = 2; i < g + 2; i++){
		visit_gold_kq[i] = 0;
	}
}
void reset_visit_map(){
	for(int i = 1; i <= n; i++){
			for(int j = 1; j <= n; j++){
				visit_map[i][j] = 1000000;
			}
		}
}
void gan_visit(){
	for(int i = 2; i < g + 2; i++){
		visit_gold_kq[i] = visit_gold[i];
	}
}
void BFS(int x, int y, int d){
	r = f = -1;
	push(x,y,d);
	visit_map[x][y] = 0;
	while (r != f){
		pop(x,y,d);
		for(int i = 0; i < 4; i++){
			int xx = x + dx[i];
			int yy = y + dy[i];
			if(xx >= 1 && xx <= n && yy >= 1 && yy <= n){
				if(map[xx][yy] != 0 && d + 1 < visit_map[xx][yy]){
					push(xx,yy,d+1);
					visit_map[xx][yy] = d + 1;
					if(map[xx][yy] == 2 || map[xx][yy] == 3 || map[xx][yy] == 4 || map[xx][yy] == 5 ) check = true;
					if(map[xx][yy] != 0 && map[xx][yy] != 1) visit_gold[map[xx][yy]] = 1;
				}
			}
		}
	
	}
}
int main(){
	//freopen("input.txt", "r", stdin);
	int T;
	cin >> T;
	for(int tc = 1; tc <= T; tc++){
		cin >> n >> g;
		for(int i = 2; i < g  +  2; i++){
			cin >> gold[0][i];
			cin >> gold[1][i];
		}
		for(int i = 1; i <= n; i++){
			for(int j = 1; j <= n; j++){
				cin >> map[i][j];
			}
		}
		for(int i = 2; i < g + 2; i++){
			map[gold[0][i]][gold[1][i]] = i;
		}
		// Solve
		reset_visit_gold_kq();
		check = false;
		int reached_gold = 0;
		int max_dis = 10000;
		for(int i = 1; i <= n; i++){
			for(int j = 1; j <= n; j++){
				if(map[i][j] == 1){
				int dem = 0;
				int max_dis_tmp = 0;
				reset_visit_map();
				reset_visit_gold();
				BFS(i,j,0);
				for(int k = 2; k < g + 2; k++){
					if(visit_gold[k] == 1) {
						dem++;
						if(visit_map[gold[0][k]][gold[1][k]] > max_dis_tmp) max_dis_tmp = visit_map[gold[0][k]][gold[1][k]];
					}
				}
				if(dem > reached_gold) {
					reached_gold = dem;
					max_dis = max_dis_tmp;
					gan_visit();

				}
				if(dem == reached_gold){
					if(max_dis_tmp < max_dis){
						max_dis = max_dis_tmp;
						gan_visit();
					}
				}
			}
			}
		}
		cout << "Case #" << tc << endl;
		if(check == false) cout << -1 << endl;
		else{
			cout << max_dis << endl;
			for(int i = 2; i < g + 2; i++){
				if(visit_gold_kq[i] == 0) cout << gold[0][i] << " " << gold[1][i] << endl;
			}
		}
	}
	return 0;
}