Untitled

package bla;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;
class Queue {
	private int maxSize;
	private int [] Array;
	private int front , rear;
	
	public Queue(int s){
		maxSize = s;
		Array = new int[maxSize];
		front = -1;
		rear = -1;
	}
	
	public boolean isEmpty(){
		if(this.front == this.rear){
			return true;
		}
		return false;
	}
	public boolean isFull(){
		if(this.rear == this.maxSize-1){
			return true;
		}
		return false;
	}
	public void Push (int x){
		Array[++rear] = x;
	}
	public int Pop(){
		front++;
		return Array[front];
	}
	public void reset(){
		front=rear=-1;
	}
}
public class Solution {
	static int N,G;
	static int gold [][];
	static int Map [][];
	static int map_gold [];
	static int vis [][];
	static Queue Qx = new Queue(10000000);
	static Queue Qy = new Queue(10000000);
	static int [] dx = {0,1,0,-1};
	static int [] dy = {1,0,-1,0};
	public static void BFS(int i,int j){
		Qx.reset();
		Qy.reset();
		resetVis();
		Qx.Push(i);
		Qy.Push(j);
		vis[i][j]=0;
		while(!Qx.isEmpty()){
			int x = Qx.Pop();
			int y = Qy.Pop();
			for (int k = 0; k < 4; k++) {
				int r = x + dx[k];
				int c = y + dy[k];
				if(r>0 && c>0 && r <= N && c <= N && Map[r][c] != 0 && vis[r][c] == -1){
					Qx.Push(r);
					Qy.Push(c);
					vis[r][c]= vis[x][y]+1;
				}
			}
		}
	}
	public static void resetVis(){
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				vis[i][j] = -1;
			}
		}
	}
	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("input.txt"));
		Scanner sc = new Scanner(System.in);
		int t = sc.nextInt();
		for (int tc = 1; tc <= t; tc++) {
			
			
			gold = new int [5][2];
			Map = new int[21][21];
			map_gold = new int [5];
			vis = new int [21][21];
			
			
			N = sc.nextInt();
			G = sc.nextInt();
			for (int i = 1; i <= G; i++) {
				int x,y;
				x = sc.nextInt();
				y = sc.nextInt();
				gold[i][0] = x;
				gold[i][1] = y;
			}
			
			for (int i = 1; i <= N; i++) {
				for (int j = 1; j <= N; j++) {
					Map[i][j] = sc.nextInt();
				}
			}
			for (int i = 1; i <= G; i++) {
				Map[gold[i][0]][gold[i][1]]=2;
			}
			
			int gold_max = 0, time_min = 99999999;
			for (int i = 1; i <= N; i++) {
				for (int j = 1; j <= N; j++) {
					int dem_gold = 0, time_gold = 0;
					if(Map[i][j]==1){
						BFS(i, j);
						for (int q = 1; q <= G; q++) {
							if(vis[gold[q][0]][gold[q][1]] != -1){
								dem_gold++;
								time_gold = Math.max(time_gold, vis[gold[q][0]][gold[q][1]]);
							}
						}
						if(dem_gold > gold_max || dem_gold == gold_max && time_gold < time_min){
							gold_max = dem_gold;
							time_min = time_gold;
							for (int k = 1; k <= 4; k++) {
								map_gold[k] = vis[gold[k][0]][gold[k][1]];
							}
						}
						resetVis();
					}
				}
			}
			if(gold_max == G){
				System.out.println("Case #"+tc);
				System.out.println(time_min);
			}else if(gold_max == 0){
				System.out.println("Case #"+tc);
				System.out.println(" -1");
			}else{
				System.out.println("Case #"+tc);
				System.out.println(time_min);
				for (int i = 1; i <= G; i++) {
					if(map_gold[i] == -1){
						System.out.println(gold[i][0]+" "+gold[i][1]);
					}
				}
			}
		}
	}
}