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++;
}
}
}
}
}
}