Untitled

import java.util.Scanner;
class index {
	int row;
	int col;

	public index(int x, int y) {
		this.row = x;
		this.col = y;

	}
}

public class Solution {
	static int timduongdingannhat(index x1 , index x2){
		rear =-1;
		front =0;
		check = new boolean[N][N];
		check[x1.row][x1.col] = true;
		push(x1);
		int cnt =1;
		while(!isempty()){
			int pt = rear - front+1;
			for(int i =0;i<pt;i++){
				index in = pop();
				for(int j =0;j<4;j++){
					int newr = in.row+dichchuyenrow[j];
					int newc = in.col+dichchuyencol[j];
					if(newr >=0 && newr <N && newc >=0 && newc <N && check[newr][newc] == false && map[newr][newc]!= 0){
						if(newr == x2.row && newc == x2.col){
							return cnt;
						}
						check[newr][newc] = true;
						index newin = new index(newr, newc);
						push(newin);
						
					}
				}
			}
			cnt++;
			
		}
		return -1;
	}
	static int N, G, rear, front;
	static index[] queue = new index[400];

	static void push(index x) {
		rear++;
		queue[rear] = x;
	}

	static index pop() {
		front++;
		return queue[front - 1];

	}

	static boolean isempty() {
		if (front == rear + 1) {
			return true;
		}
		return false;
	}
	static int[] dichchuyenrow = {-1,0,1,0};
	static int[] dichchuyencol = {0,1,0,-1};
	

	static int[][] map,check5;
	static index[] mangluuvang;
	static boolean[][] check;
	

	public static void main(String[] args)throws Exception {
	//	System.setIn(new FileInputStream("input.txt"));
		Scanner scanner = new Scanner(System.in);
		int T = scanner.nextInt();
		for (int t = 1; t <= T; t++) {
			System.out.println("Case #"+t);
			N = scanner.nextInt();
			G = scanner.nextInt();
			mangluuvang = new index[G];
			map = new int[N][N];
			check5 = new int[N][N];
			int count = 0;
			for (int i = 0; i < G; i++) {
				int r = scanner.nextInt()-1;
				int c = scanner.nextInt()-1;
				check5[r][c] = 1;
				index in = new index(r, c);
				mangluuvang[count] = in;
				count++;
			}
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					map[i][j] = scanner.nextInt();

				}
			}
			for (int i = 0; i < G; i++) {
				map[mangluuvang[i].row][mangluuvang[i].col] = 2;
			}
			int min = Integer.MAX_VALUE;
			int min1 = Integer.MAX_VALUE;
			int r =0;
			int c =0;
			for(int i =0;i< N ; i++){
				for(int j =0;j<N;j++){
					if(map[i][j] == 1){
						int max =0;
						int dem =0;
						index a = new index(i, j);
						for(int q =0;q<G;q++){
							
							int kc = timduongdingannhat(a, mangluuvang[q]);
							
							if(kc!= -1){
								check5[mangluuvang[q].row][mangluuvang[q].col] ++;
								if(kc > max){
									max = kc;
								
								}
								
							}
							else {
								dem++;
							}
						}
						if(dem==min1){
                            
                            
							if(max < min && max !=0){
								min = max;
								r = i;
								c = j;
								
							}
						}
						if(dem< min1){
							min1 = dem;
							min = max;
							r = i;
							c = j;
						}
						
						
						
					}
					else {
						continue;
					}
				}
			}
			index rs = new index(r, c);
			
//			if(min1 >0){
//				System.out.println("-1");
//			}
//
//			else {
//				System.out.println(min);
//			}
			//int check3 =0;
			int dem =0;
			for(int i =0;i<N;i++){
				for(int j =0;j<N;j++){
					if(check5[i][j] == 1){
						dem++;
//					System.out.println((i+1)+" "+(j+1));
					}
				}
				
			}
			if(dem == G){
				System.out.println("-1");
			}
			else {
				System.out.println(min);
				for(int i1 = 0;i1<G;i1++){
					if(timduongdingannhat(rs, mangluuvang[i1])== -1){
						System.out.println((mangluuvang[i1].row+1)+" "+(mangluuvang[i1].col+1));
					}
				}
				
			}
			

		}

	}

}