Untitled

public class Solution {

	static PoitnCs[] golds;
	static int[][] map;
	static int[][] step;
	static int minDis;
	static Queue<PoitnCs> qt;
	static int n;
	static int[] dx = { -1, 0, 1, 0 };
	static int[] dy = { 0, 1, 0, -1 };

	public static void main(String args[]) throws Exception {
		Scanner sc = new Scanner(System.in);

		int T = sc.nextInt();
		qt = new Queue<Solution.PoitnCs>();

		for (int tc = 1; tc <= T; tc++) {

			n = sc.nextInt();
			int g = sc.nextInt();

			minDis = 9999;

			golds = new PoitnCs[g];
			for (int i = 0; i < g; i++) {
				golds[i] = new PoitnCs(sc.nextInt(), sc.nextInt());
			}

			map = new int[n + 1][n + 1];
			for (int i = 1; i <= n; i++) {
				for (int j = 1; j <= n; j++) {
					map[i][j] = sc.nextInt();
				}
			}
			System.out.println(solve());
		}
	}

	static int solve() throws Exception {
		for (int i = 1; i <= map.length - 1; i++) {
			for (int j = 1; j <= map.length - 1; j++) {
				if (map[i][j] != 0) {
					step = new int[map.length][map.length];
					bfs(i, j);

					boolean canGoAllGolds = true;
					for (int k = 0; k < golds.length; k++) {
						if (step[golds[k].x][golds[k].y] == 0) {
							canGoAllGolds = false;
							break;
						}
					}

					if (!canGoAllGolds) {
						continue;
					}

					int maxDistanceToGold = 0;
					for (int k = 0; k < golds.length; k++) {
						int stepGold = step[golds[k].x][golds[k].y] - 1;
						maxDistanceToGold = Math.max(maxDistanceToGold,
								stepGold);
					}
					minDis = Math.min(minDis, maxDistanceToGold);
				}
			}
		}
		return (minDis == 9999) ? -1 : minDis;
	}

	private static void bfs(int x, int y) throws Exception {
		qt.reset();
		qt.enQueue(new PoitnCs(x, y));
		step[x][y] = 1;
		PoitnCs tmp;
		while (!qt.isEmpty()) {
			tmp = qt.peek();
			qt.deQueue();

			for (int i = 0; i < dx.length; i++) {
				int xx = tmp.x + dx[i];
				int yy = tmp.y + dy[i];
				if (xx < 1 || xx >= map.length || yy < 1 || yy >= map.length
						|| map[xx][yy] == 0) {
					continue;
				}
				if (step[xx][yy] == 0) {
					step[xx][yy] = step[tmp.x][tmp.y] + 1;
					qt.enQueue(new PoitnCs(xx, yy));
				}
			}
		}
	}