#include <iostream>
#include <fstream>
#define MIN 99999999
using namespace std;
int n, g;
int arr[21][21];
int TG[10][21][21];
int visited[21][21];
int dR[4] = { -1, 0, 1, 0 };
int dC[4] = { 0, 1, 0, -1 };
int visitedV[10];
ifstream input("input.txt");
fstream output;
typedef struct Point {
int x, y;
};
Point G[10];
typedef struct Queue {
int front, rear;
Point data[10001];
};
void init(Queue& Q) {
Q.front = Q.rear = -1;
}
void push(Queue& Q, Point value) {
Q.rear++;
Q.data[Q.rear] = value;
}
Point top(Queue& Q) {
Point temp;
Q.front++;
temp = Q.data[Q.front];
Q.front--;
return temp;
}
void pop(Queue& Q) {
Q.front++;
}
bool empty(Queue& Q) {
if (Q.front == Q.rear)
return true;
return false;
}
Queue Q;
void BFS(int index, Point P) {
init(Q);
push(Q, P);
visited[P.x][P.y] = 1;
TG[index][P.x][P.y] = 0;
while (!empty(Q)) {
Point P1;
P1 = top(Q);
pop(Q);
for (int k = 0; k < 4; k++) {
int x = P1.x + dR[k];
int y = P1.y + dC[k];
if (x >= 1 && x <= n && y >= 1 && y <= n && visited[x][y] == 0 && arr[x][y] != 0) {
visited[x][y] = 1;
TG[index][x][y] = TG[index][P1.x][P1.y] + 1;
Point P2;
P2.x = x;
P2.y = y;
push(Q, P2);
}
}
}
}
void reset1() {
for (int v = 1; v <= g; v++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
TG[v][i][j] = -1;
}
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
arr[i][j] = 0;
}
}
}
void reset2() {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
visited[i][j] = 0;
}
}
}
void reset3() {
for (int i = 1; i <= g; i++) {
visitedV[i] = 0;
}
}
void in() {
input >> n >> g;
reset1();
int gx, gy;
for (int i = 1; i <= g; i++) {
input >> gx >> gy;
G[i].x = gx;
G[i].y = gy;
arr[gx][gy] = 1;
arr[gy][gx] = 1;
}
int m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
input >> m;
arr[i][j] += m;
}
}
}
void sort() {
for (int i = 1; i < g; i++) {
int sumI = G[i].x + G[i].y;
for (int j = i + 1; j <= g; j++) {
int sumJ = G[j].x + G[j].y;
if (sumI > sumJ) {
swap(G[i].x, G[j].x);
swap(G[i].y, G[j].y);
}
}
}
}
int main() {
output.open("output.txt");
int t;
input >> t;
for (int tc = 1; tc <= t; tc++) {
in();
sort();
for (int v = 1; v <= g; v++) {
cout << G[v].x << " " << G[v].y << endl;
}
for (int i = 1; i <= g; i++) {
int x = G[i].x;
int y = G[i].y;
Point P;
P.x = x;
P.y = y;
reset2();
BFS(i, P);
}
int MinTG = MIN;
int MaxV = -1;
int visitedV[10] = {};
for (int v1 = 1; v1 <= g; v1++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (TG[v1][i][j] >= 1) {
int countV = 0;
int MaxTG = -1;
int arrIndex[10];
int index = 1;
for (int v2 = 1; v2 <= g; v2++) {
if (TG[v2][i][j] != -1) {
countV++;
arrIndex[index++] = v2;
MaxTG = max(MaxTG, TG[v2][i][j]);
}
}
if (MaxV < countV) {
reset3();
for (int k = 1; k < index; k++)
visitedV[arrIndex[k]] = 1;
MaxV = countV;
MinTG = MaxTG;
}
if (MaxV == countV) {
if (MinTG > MaxTG) {
reset3();
for (int k = 1; k < index; k++)
visitedV[arrIndex[k]] = 1;
MinTG = MaxTG;
}
}
}
}
}
}
//cout << "MinTG: " << MinTG << endl;
output << "Case #" << tc << endl;
if (MinTG == MIN) {
output << "-1" << endl;
}
else {
output << MinTG << endl;
for (int v = 1; v <= g; v++) {
if (visitedV[v] == 0)
output << G[v].x << " " << G[v].y << endl;
}
}
cout << endl;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cout << arr[i][j] << " ";
}
cout << endl;
}
cout << endl;
for (int v = 1; v <= g; v++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cout << TG[v][i][j] << " ";
}
cout << endl;
}
cout << endl;
}
}
}