Untitled

package hugo_dao_vang_1;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Solution {
	static int n, res, g, check, mo;
	static int[][] a, visit, golden, value;
	static int[] dx = { 0, 1, 0, -1 }, dy = { 1, 0, -1, 0 };
	static int[] gx = new int[5], gy = new int[5];
	static int[] nox = new int[5], noy = new int[5];
	static int[] qx = new int[1000], qy = new int[1000];

	static boolean checkOut(int x, int y) {
		if (x < 0 || x >= n || y < 0 || y >= n)
			return false;
		return true;
	}

	static void BFS(int x, int y) {
		visit = new int[n][n];
		value = new int[n][n];
		int front = 0, rear = 1;
		qx[front] = x;
		qy[front] = y;
		visit[x][y] = 1;
		while (front < rear) {
			int xt = qx[front], yt = qy[front], c = value[xt][yt];
			for (int i = 0; i < 4; i++) {
				int nx = xt + dx[i], ny = yt + dy[i];
				if (checkOut(nx, ny) && a[nx][ny] == 1 && visit[nx][ny] == 0) {
					qx[rear] = nx;
					qy[rear] = ny;
					rear++;
					visit[nx][ny] = 1;
					value[nx][ny] = c + 1;
				}
			}

			front++;
		}

		int max = 0;
		int dem = 0;

		for (int i = 0; i < g; i++) {
			if (value[gx[i]][gy[i]] > max) {
				max = value[gx[i]][gy[i]];
			}
			if (visit[gx[i]][gy[i]] == 1) {
				dem++;
			}

		}

		if((dem > mo) || ((dem == mo && dem != 0) && max < res)){
			res = max;
			mo = dem;
			int count = 0;
			for (int i = 0; i < g; i++) {
				if (visit[gx[i]][gy[i]] == 0) {
					nox[count] = gx[i];
					noy[count] = gy[i];
					count++;
				} 

			}
		}

	}

	public static void main(String[] args) {
		try {
			System.setIn(new FileInputStream("input.txt"));
		} catch (FileNotFoundException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}

		Scanner scanner = new Scanner(System.in);
		int test = scanner.nextInt();
		for (int t = 1; t <= test; t++) {
			n = scanner.nextInt();
			g = scanner.nextInt();
			a = new int[n][n];
			golden = new int[n][n];
			for (int i = 0; i < g; i++) {
				gx[i] = scanner.nextInt() - 1;
				gy[i] = scanner.nextInt() - 1;
				golden[gx[i]][gy[i]] = 1;
			}
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					a[i][j] = scanner.nextInt();
				}
			}

			res = Integer.MAX_VALUE;
			mo = 0;

			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					if (a[i][j] == 1 && golden[i][j] == 0) {
						BFS(i, j);
					}
				}
			}

			if (mo == 0) {
				System.out.println("Case #" + t + "\n" + -1);
			} else {
				System.out.println("Case #" + t + "\n" + res);
				for (int i = 0; i < g - mo; i++) {
					System.out.println((nox[i] + 1) + " " + (noy[i] + 1));
				}
			}
			// System.out.println("-----------");

		}
		scanner.close();
	}
}