Untitled

#include <iostream>
#define INF 10000000
using namespace std;
int mQ[100000];
int A[21][21], visit[21][21],visit0[21][21], visit1[21][21], visit2[21][21], visit3[21][21], visitA[21][21];
int m, G;
int mangVang[4][2],dske[4][3],index[4];
int f, r;
int maxx, answer;
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };

void push(int x) {
	r++;
	mQ[r] = x;
}

int pop() {
	f++;
	return mQ[f];
}
void reset() {
	f = r = -1;
	for (int i = 1;i <= m;i++) {
		for (int j = 1;j <= m;j++) {
			visit[i][j] = 0;
		}
	}
}
void input() {
	cin >> m >> G;
	for (int i = 0;i < G;i++) {
		cin >> mangVang[i][0] >> mangVang[i][1];
	}
	for (int i = 1;i <= m;i++) {
		for (int j = 1;j <= m;j++) {
			cin >> A[i][j];
			visit[i][j]=visit0[i][j]= visit1[i][j]=visit2[i][j]=visit3[i][j]= visitA[i][j] = 0;
		}
	}
	for (int i = 0;i < G;i++) {
		A[mangVang[i][0]][mangVang[i][1]] = 2;index[i] = 0;
		for (int j = 0;j < 3;j++) {
			dske[i][j] = 0;
		}
	}
}
void BFS(int x, int y) {
	reset();
	push(x);
	push(y);
	visit[x][y] = 1;
	while (f != r) {
		int x = pop();
		int y = pop();
		for (int i = 0;i < 4;i++) {
			int xx = x + dx[i];
			int yy = y + dy[i];
			if (xx < 1|| xx > m || yy < 1 || yy > m || A[xx][yy] == 0) continue;
			if (visit[xx][yy] == 0) {
				push(xx);
				push(yy);
				visit[xx][yy] = visit[x][y] + 1;
			}
			else if (visit[xx][yy] > visit[x][y] + 1) {
				push(xx);
				push(yy);
				visit[xx][yy] = visit[x][y] + 1;
			}
		}
	}
	
}
int main() {
	freopen("input.txt", "r", stdin);
	int t;
	cin >> t;
	for (int tc = 1;tc <= t;tc++) {
		input();
		
		for (int i = 0;i < G;i++) {
			BFS(mangVang[i][0], mangVang[i][1]);
			if (i == 0) {
				for (int j = 0;j < G;j++) {
					if (j != 0 && visit[mangVang[j][0]][mangVang[j][1]] != 0) {
						dske[0][index[0]] = j;
						index[0]++;
					}
				}
				for (int k = 1;k<= m;k++) {
					for (int j = 1;j <= m;j++) {
						visit0[k][j] = visit[k][j];
						visitA[k][j] = visit[k][j];
					}
				}
			}
			else if (i == 1) {
				for (int j = 0;j < G;j++) {
					if (j != 1 && visit[mangVang[j][0]][mangVang[j][1]] != 0) {
						dske[1][index[1]] = j;
						index[1]++;
					}
				}
				for (int k = 1;k <= m;k++) {
					for (int j = 1;j <= m;j++) {
						visit1[k][j] = visit[k][j];
						if (visitA[k][j] < visit[k][j])
							visitA[k][j] = visit[k][j];
					}
				}
			}
			else if (i == 2) {
				for (int j = 0;j < G;j++) {
					if (j != 2 && visit[mangVang[j][0]][mangVang[j][1]] != 0) {
						dske[2][index[2]] = j;
						index[2]++;
					}
				}
				for (int k = 1;k <= m;k++) {
					for (int j = 1;j <= m;j++) {
						visit2[k][j] = visit[k][j];
						if(visitA[k][j] < visit[k][j])
							visitA[k][j] = visit[k][j];
					}
				}
			}
			else if (i == 3) {
				for (int j = 0;j < G;j++) {
					if (j != 3 && visit[mangVang[j][0]][mangVang[j][1]] != 0) {
						dske[3][index[3]] = j;
						index[3]++;
					}
				}
				for (int k = 1;k <= m;k++) {
					for (int j = 1;j <= m;j++) {
						visit3[k][j] = visit[k][j];
						if (visitA[k][j] < visit[k][j])
							visitA[k][j] = visit[k][j];
					}
				}
			}
		}
		int a=0;
		answer = -1;
		for (int j = 0;j < G;j++) {
			if (answer < index[j]) {
				answer = index[j];
				a = j;
			}
		}

		int minn = INF;
		if (answer != 0) {
			if (a == 0) {
				for (int i = 1;i <= m;i++) {
					for (int j = 1;j <= m;j++) {
						if (visitA[i][j] < minn && visit0[i][j] != 0 )
							minn = visitA[i][j];
					}
				}
			}
			else if (a == 1) {
				for (int i = 1;i <= m;i++) {
					for (int j = 1;j <= m;j++) {
						if (visitA[i][j] < minn && visit1[i][j] != 0 )
							minn = visitA[i][j];
					}
				}
			}
			else if (a == 2) {
				for (int i = 1;i <= m;i++) {
					for (int j = 1;j <= m;j++) {
						if (visitA[i][j] < minn && visit2[i][j] != 0)
							minn = visitA[i][j];
					}
				}
			}
		}
		else {
			a = -1;
			for (int i = 1;i <= m;i++) {
				for (int j = 1;j <= m;j++) {
					if (visit0[i][j] < minn && visit0[i][j] != 0&&visit0[i][j]>1)
						minn = visit0[i][j];
				}
			}
			if (minn != INF) {
				a = 0;
			}
			if (minn == INF) {
				for (int i = 1;i <= m;i++) {
					for (int j = 1;j <= m;j++) {
						if (visit1[i][j] < minn && visit1[i][j] != 0 && visit1[i][j]>1)
							minn = visit1[i][j];
					}
				}
			}
			if (minn != INF&&a==-1) {
				a = 1;
			}
			if (minn == INF&&G==3) {
				for (int i = 1;i <= m;i++) {
					for (int j = 1;j <= m;j++) {
						if (visit2[i][j] < minn && visit2[i][j] != 0 && visit2[i][j]>1)
							minn = visit2[i][j];
					}
				}
			}
			if (minn != INF && a == -1) {
				a = 2;
				
			}
			if (minn == INF && G == 4) {
				for (int i = 1;i <= m;i++) {
					for (int j = 1;j <= m;j++) {
						if (visit3[i][j] < minn && visit3[i][j] != 0 && visit3[i][j] > 1)
							minn = visit3[i][j];
					}
				}
			}
			if (minn != INF && a == -1) {
				a = 3;
			}
		}
		if (answer == 0&&a==-1) {			
				cout << "Case #" << tc << endl << -1 << endl;
		}
		else if(index[a]==4)
			cout << "Case #" << tc << endl << minn-1 << endl;
		else {
			cout << "Case #" << tc << endl << minn-1 << endl;
			for (int i = 0;i < G;i++) {
				bool check = true;
				if (i != a) {
					for (int k = 0;k < index[a];k++) {
						if (dske[a][k] == i) {
							check = false; break;
						}
					}
					if (check) {
						cout << mangVang[i][0] << " " << mangVang[i][1] << endl;
					}
				}
			}
		}
		cout << endl;
	}
	return 0;
}