Untitled

package d22;

import java.util.Scanner;

public class HugoDaoVang1 {
	public static int n,g,row,col;
	public static int arr[][] =  new int[25][25];
	public static int res[][][] = new int[25][25][5];
	public static int G[][] = new int [5][2];
	public static int que[][] = new int[10005][3];
	public static int X[] = {0,0,1,-1};
	public static int Y[] = {1,-1,0,0};
	public static int check[][] = new int[25][25];
	public static int check_g[] = new int [5];
	public static int so_mo_vang_max,chi_phi_min,x_res,y_res;
	public static void BFS(int id_g){
		int l=0,r=0;
		que[l][0] = G[id_g][0];
		que[l][1] = G[id_g][1];
		que[l][2] = 0;
		res[G[id_g][0]][G[id_g][1]][id_g] = 0;
		res[G[id_g][0]][G[id_g][1]][0] +=1;
		check[G[id_g][0]][G[id_g][1]]=1;
		int fr_x,fr_y,fr_step;
		while(l<=r){
			fr_x = que[l][0];
			fr_y = que[l][1];
			fr_step = que[l][2];
			for(int i=0;i<4;i++){
				if(fr_x+X[i]>=1 && fr_x+X[i]<=n && fr_y+Y[i]>=1 && fr_y+Y[i]<=n
						&& check[fr_x+X[i]][fr_y+Y[i]]==0
						&& arr[fr_x+X[i]][fr_y+Y[i]]!=0){
					r++;
					que[r][0] = fr_x+X[i];
					que[r][1] = fr_y+Y[i];
					que[r][2] = fr_step+1;
					check[fr_x+X[i]][fr_y+Y[i]]=1;
					res[fr_x+X[i]][fr_y+Y[i]][id_g] = que[r][2];
					res[fr_x+X[i]][fr_y+Y[i]][0]+=1;
				}
			}
			l++;
		}
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int t = sc.nextInt();
		for(int test=1;test<=t;test++){
			n = sc.nextInt();
			g = sc.nextInt();
			for(int i=1;i<=g;i++){
				row = sc.nextInt();
				col = sc.nextInt();
				G[i][0] = row;
				G[i][1] = col;
				check_g[i] = 0;
			}
			for(int i=1;i<=n;i++){
				for(int j=1;j<=n;j++){
					arr[i][j] = sc.nextInt(); // 0 la da, 1 la di duoc
				}
			}
			for(int i=1;i<=g;i++){
				arr[G[i][0]][G[i][1]] = 2; // 2 la co vang
			}
			
			//solve
			for(int i=0;i<=n;i++){
				for(int j=0;j<=n;j++){
					for(int k=0;k<=g;k++){
						res[i][j][k] = 0;
					}
				}
			}
			for(int i=1;i<=g;i++){
				for(int j=0;j<=n;j++){
					for(int k=0;k<=n;k++){
						check[j][k]=0;
					}
				}
				BFS(i);
			}
//			for(int k=1;k<=g;k++){
//				for(int i=1;i<=n;i++){
//					for(int j=1;j<=n;j++){
//						System.out.print(res[i][j][k]+" ");
//					}
//					System.out.println();
//				}
//				System.out.println("-------------------------------------------");
//			}
			int ok = 0;
			so_mo_vang_max = 0;
			chi_phi_min = 0;
			x_res = 0;
			y_res = 0;
			for(int i=1;i<=n;i++){
				for(int j=1;j<=n;j++){
					if(arr[i][j]==1){
						int tmp_max = 0;
						for(int k=1;k<=g;k++){
							if(res[i][j][k]!=0){
								if(tmp_max<res[i][j][k]) tmp_max = res[i][j][k];
								if(check_g[k]==0){
									ok+=1;
									check_g[k]=1;
								}
							}
						}
						if(so_mo_vang_max<res[i][j][0]){
							so_mo_vang_max = res[i][j][0];
							chi_phi_min = tmp_max;
							x_res = i;
							y_res = j;
							
						}else if(so_mo_vang_max==res[i][j][0]){
							if(chi_phi_min>tmp_max){
								chi_phi_min = tmp_max;
								x_res = i;
								y_res = j;
							}
						}
					}
				}
			}
			System.out.println("Case #"+test);
			if(ok==0){
				System.out.println("-1");
			}else{
				System.out.println(chi_phi_min);
				for(int i=1;i<=g;i++){
					if(res[x_res][y_res][i]==0){
						System.out.println(G[i][0]+" "+G[i][1]);
					}
				}
			}
		}
	}
}