Untitled

#include<iostream>
using namespace std;
int n, g;
int vtdx, vtdy, vtcx, vtcy;
int data[1005][1005];
int datav[5][2];
int khov[5] = {999999, 999999, 999999, 999999, 999999};
int trai[5][2];
int datavktd[5][5];
int visit[1005][1005];
int dx1[] = {0, -1, 0, 1};
int dy1[] = {-1, 0, 1, 0};
int front, rear;

void init() {
	front = rear = 0;
}

void rskv() {
	for (int i =0; i <= g; i++) {
		khov[i] = 999999;
	}
}

struct toado
{
	int x,y;
};

toado queu[9000000];

void push(int xx, int yy) {
	queu[rear].x = xx;
	queu[rear].y = yy;
	rear ++;
}

toado pop() {
	toado t = queu[front];
	front ++;
	return t;
}

void BFS(int x, int y) {
	int maxx = 0;
	visit[x][y] = 0;
	push(x,y);
	while (front < rear) {
		toado vitri = pop();
		for (int i = 0; i < 8; i ++) {
			int xn = vitri.x + dx1[i];
			int yn = vitri.y + dy1[i];
			if (xn > 0 && xn <= n && yn >0 && yn <= n && visit[xn][yn] == 0 && data[xn][yn] == 1) {
				visit[xn][yn] = visit[vitri.x][vitri.y] + 1;
				push(xn, yn);
			}
		}
	}
	int dem= 0;
	for (int i = 0; i < g; i++) {
		if (visit[datav[i][0]][datav[i][1]] > 0) {
			dem ++;
			if (visit[datav[i][0]][datav[i][1]] > maxx) {
				maxx = visit[datav[i][0]][datav[i][1]] ;
			}
		}
		
	}

	if (khov[dem] > maxx) {
		khov[dem] = maxx;
		trai[dem][0] = x;
		trai[dem][1] = y;
		int demm = 0;
		for (int i = 0; i < g; i++) {
			if (visit[datav[i][0]][datav[i][1]] == 0) {
				demm ++;
				datavktd[dem][demm] = i;
			}
		}

	}
}

void rs() {
	for (int i = 1; i <= n; i++) {
		for (int j  = 1; j <= n; j++) {
			visit[i][j] = 0;
		}
	}
}

int main() {
	int sl;
	ios::sync_with_stdio(false);
	freopen("input.txt", "r", stdin);
	cin >> sl;
	for(int stt = 1; stt <= sl; stt ++) {
		cin >> n >> g;
		int xx, yy;
		rskv();
		for (int i = 1; i <= n; i++) {
			for (int j  = 1; j <= n; j++) {
				data[i][j] = 0;
				visit[i][j] = 0;
			}
		}
		for (int i = 0; i < g; i++) {
			cin >> datav[i][0] >> datav[i][1];
		}

		for (int i = 1; i <= n; i++) {
			for (int j  = 1; j <= n; j++) {
				cin >> data[i][j];
			}
		}
		bool ktra = false;
		for (int i = 1; i <= n; i++) {
			for (int j  = 1; j <= n; j++) {
				bool tk = true;
				for (int ii = 0; ii < g; ii++) {
					if (datav[ii][0] == i && datav[ii][1] == j) {
						tk = false;
						break;
					}
				}

				if (data[i][j] == 1 && tk) {
					rs();
					BFS(i,j);		
				}
			}
		}
		cout <<"Case #"<<stt<<endl;
		for (int i = g; i > 0; i--) {
			if (khov[i] != 999999) {
				ktra = true;
				cout << khov[i] <<endl;
				for (int j = 1; j <=g-i; j ++) {
					cout << datav[datavktd[i][j]][0]<<" "<<datav[datavktd[i][j]][1]<<endl;
				}
				break;
			}
		//	cout <<"i="<<i<<" "<<khov[i]<<endl;
		}
		if (ktra == false) cout << -1<<endl;

	}
	return 0;
}