Untitled

#1: 1 / #2: 2 / #3: 2 / #4: 7 / #5: 3 / 1 9 / #6: 8 / #7: 2 / #8: 4 / #9: 6 / #10: 1 / 8 4 / #11: 1 / 4 3 / 4 5 / 6 10 / #12: 1 / #13: 4 / 6 8 / #14: 6 / 3 9 / #15: 1 / 1 7 / 9 10 / 7 2 / #16: 1 / 3 6 / #17: 8 / #18: 1 / 10 10 / #19: 3 / 6 8 / #20: 7 / #21: 7 / #22: 2 / #23: 10 / #24: 9 / #25: 2 / 11 10 / 10 10 / #26: 6 / #27: 1 / 2 11 / #28: 1 / 9 8 / #29: 8 / #30: 3 / #31: 5 / #32: 10 / #33: 12 / #34: 12 / #35: 5 / 2 2 / #36: 13 / #37: 12 / 6 10 / 4 15 / #38: 8 / #39: 3 / #40: 11 / #41: 1 / 5 14 / #42: 8 / #43: 1 / 18 14 / #44: 10 / #45: 10 / 20 13 / #46: 8 / 18 2 / #47: 7 / #48: -1 / #49: 11 / #50: 1 / 17 2

public class Solution {
	static final int MS = 30;
	static int n, g, maxx, minn, cg;
	static int[] gx = new int[MS];
	static int[] gy = new int[MS];
	static int[][] m = new int[MS][MS];
	static int[][] ig = new int[MS][MS];
	static int[][] check = new int[MS][MS];
	static boolean[] c = new boolean[MS];
	static boolean[] c_tmp = new boolean[MS];
	static int[] dx = { -1, 0, 1, 0 };
	static int[] dy = { 0, 1, 0, -1 };

	static Queue<Point> q;

	static void BFS(int xh, int yh) {

		maxx = 0;
		cg = 0;
		c_tmp = new boolean[g];
		check = new int[MS][MS];

		q.reset();
		q.enQueue(new Point(xh, yh));
		check[xh][yh] = 1;

		Point p;
		while (!q.isEmpty()) {
			p = q.peek();
			q.deQueue();
			for (int i = 0; i < 4; i++) {
				int xx = p.x + dx[i];
				int yy = p.y + dy[i];
				if (isSafe(xx, yy) && check[xx][yy] == 0) {
					check[xx][yy] = check[p.x][p.y] + 1;
					q.enQueue(new Point(xx, yy));
					if (m[xx][yy] == 9) {
						cg++;
						c_tmp[ig[xx][yy]] = true;
						maxx = Math.max(maxx, check[xx][yy] - 1);
					}
				}
			}
		}
	}

	private static boolean isSafe(int xx, int yy) {
		if (xx >= 1 && xx <= n && yy >= 1 && yy <= n && m[xx][yy] != 0) {
			return true;
		}
		return false;
	}

	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		q = new Queue<>();
		for (int tc = 1; tc <= T; tc++) {
			n = sc.nextInt();
			g = sc.nextInt();
			for (int i = 0; i < g; i++) {
				gx[i] = sc.nextInt();
				gy[i] = sc.nextInt();
				ig[gx[i]][gy[i]] = i;
				c[i] = false;
			}
			for (int i = 1; i <= n; i++) {
				for (int j = 1; j <= n; j++) {
					m[i][j] = sc.nextInt();
				}
			}
			for (int i = 0; i < g; i++) {
				m[gx[i]][gy[i]] = 9;
			}

			maxx = 0;
			minn = 999999;
			int sl = 0;
			for (int i = 1; i <= n; i++) {
				for (int j = 1; j <= n; j++) {
					if (m[i][j] == 1) {
						BFS(i, j);
						if (cg > sl) {
							sl = cg;
							minn = maxx;
							for (int k = 0; k < g; k++) {
								c[k] = c_tmp[k];
							}
						} else if (cg == sl) {
							if (maxx != 0) {
								if (minn > maxx) {
									minn = maxx;
									for (int k = 0; k < g; k++) {
										c[k] = c_tmp[k];
									}
								}
							}
						}
					}
				}
			}
			System.out.println("Case #" + tc);
			if (minn == 999999) {
				System.out.println(-1);
			} else {
				System.out.println(minn);
				for (int i = 0; i < g; i++) {
					if (!c[i]) {
						System.out.println(gx[i] + " " + gy[i]);
					}
				}
			}
		}
	}

}