Untitled

import java.util.Scanner;

public class Solution {
	static int n;
	static int m;
	static int[][] a;
	static int[][] vang;
	static int[] tansuat;
	static int[] tdx;
	static int[] tdy;
	static int k;
	static int[][] visit;
	static int[][] c;
	static int[][] b;
	static int[] d1 = {-1,1,0,0};
	static int[] d2 = {0,0,-1,1};
	
	public static void main(String[] args)  {
		//System.setIn(new FileInputStream("src/Hugo_Dao_Vang_1/input.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for(int test_case = 1; test_case <= T; test_case++){
			n = sc.nextInt();
			m = sc.nextInt();
			a = new int[n][n];
			b = new int[n][n];
			c = new int[n][n];
			vang = new int[n][n];
			visit = new int[n][n];
			tansuat = new int[4];
			tdx = new int[4];
			tdy = new int[4];
			
			k = 0;
			for(int i = 0; i < m; i++){
				int l = sc.nextInt()-1;
				int r = sc.nextInt()-1;
				vang[l][r] = 1;
				tdx[k] = l;
				tdy[k] = r;
				k++;
			}
			
			for(int i = 0; i < n; i++){
				for(int j = 0; j < n; j++){
					a[i][j] = sc.nextInt();
					b[i][j] = -100;
				}
			}
			
			for(int i = 0; i < k; i++){
				bfs(tdx[i], tdy[i]);
				
				/*for(int i1 = 0; i1 < n; i1++){
					for(int j1 = 0; j1 < n; j1++){
						System.out.print(visit[i1][j1] + " ");
					}
					System.out.println();
				}
				System.out.println();*/
				
				for(int j = 0; j < k; j++){
					if(visit[tdx[j]][tdy[j]] == 1 && check(tdx[j], tdy[j])){
						tansuat[i]++;
					}
				}
				update();
			}
			
			/*for(int i = 0; i < k; i++){
				System.out.println(tansuat[i]);
			}*/
			
			
			int max = 0;
			for(int i = 0; i < k; i++){
				if(max < tansuat[i]){
					max = tansuat[i];
				}
			}
			
			int u = -1;
			for(int i = 0; i < k; i++){
				if(tansuat[i] == max){
					u = i;
					break;
				}
			}	
			
			update();
			bfs(tdx[u], tdy[u]);
			
			for(int i = 0; i < k; i++){
				if(visit[tdx[i]][tdy[i]] != 1){
					tansuat[i] = 0;
				}
			}	
			update();
			
			for(int i = 0; i < k; i++){
				if(tansuat[i] == max){
					bfsTinh(tdx[i], tdy[i]);
					if(i==0){
						gan();
					}
					update();
				}
			}
			
			int min = Integer.MAX_VALUE;
			for(int i = 0; i < n; i++){
				for(int j = 0; j < n; j++){
					if(min > c[i][j] && c[i][j] != 0 && vang[i][j] != 1){
						min = c[i][j];
					}
				}
			}
			
			
			/*for(int i = 0; i < n; i++){
				for(int j = 0; j < n; j++){
					System.out.print(c[i][j] + " ");
				}
				System.out.println();
			}*/
			
			System.out.println("Case #" + test_case);
			if(min == Integer.MAX_VALUE){
				System.out.println(-1);
			}else{
				System.out.println(min);
				for(int i = 0; i < k; i++){
					if(tansuat[i] == 0){
						System.out.println((tdx[i]+1) + " " + (tdy[i]+1));
					}
				}
			}
		}
	}
	
	public static void update(){
		for(int i = 0; i < n; i++){
			for(int j = 0; j < n; j++){
				visit[i][j] = 0;
				b[i][j] = 0;
			}
		}
	}
	
	public static void gan(){
		for(int i = 0; i < n; i++){
			for(int j = 0; j < n; j++){
				c[i][j] = b[i][j];
			}
		}
	}
	
	public static void bfs(int u, int v){
		int[] q = new int[405];
		int[] w = new int[405];
		int l = 0, r = 0;
		visit[u][v] = 1;
		q[r] = u;
		w[r] = v;
		r++;
		while(l < r){
			int x = q[l]; int y = w[l]; l++;
			for(int i = 0; i < 4; i++){
				int xx = x+d1[i];
				int yy = y+d2[i];
				
				if(xx>=0 && yy >=0 && xx<n && yy<n){
					if(visit[xx][yy] == 0 && a[xx][yy] != 0){
						visit[xx][yy] = 1;
						q[r] = xx;
						w[r] = yy;
						r++;
					}
				}
			}
		}
	}
	
    public static boolean kt(){
    	for(int i = 0; i < k; i++){
    		if(tansuat[i] != 0){
    			return false;
    		}
    	}
    	return true;
    }
	
	public static boolean check(int u, int v){
		visit[u][v] = 0;
		for(int i = 0; i < n; i++){
			for(int j = 0; j < n; j++){
				if(visit[i][j] != 0){
					return true;
				}
			}
		}
		return false;
	}
	
	public static void bfsTinh(int u, int v){
		int[] q = new int[405];
		int[] w = new int[405];
		int l = 0, r = 0;
		b[u][v] = 0;
		visit[u][v] = 1;
		q[r] = u;
		w[r] = v;
		r++;
		while(l < r){
			int x = q[l]; int y = w[l]; l++;
			for(int i = 0; i < 4; i++){
				int xx = x+d1[i];
				int yy = y+d2[i];
				
				if(xx>=0 && yy >=0 && xx<n && yy<n){
					if(a[xx][yy] != 0 && visit[xx][yy] == 0){
						visit[xx][yy] = 1;
						b[xx][yy] = b[x][y] + 1;
						if(c[xx][yy] < b[xx][yy]){
							c[xx][yy] = b[xx][yy];
						}
						q[r] = xx;
						w[r] = yy;
						r++;
					}
				}
			}
		}
	}
}