Untitled

#include <iostream>
using namespace std;

#define MAX_SIZE 10000000
int front = -1;
int rear = -1;
int Arx[MAX_SIZE];
int Ary[MAX_SIZE];
int Id[MAX_SIZE];

class queue {
public:
	bool isEmpty();
	void push(int arx, int ary, int id);
	void pop();
	void peek(int &arx, int &ary, int &id);
};

bool queue :: isEmpty()
{
	if(front == rear)
	{
		return true;
	}
	return false;
}

void queue :: push(int arx, int ary, int id)
{
	front++;
	Arx[front] = arx;
	Ary[front] = ary;
	Id[front] = id;
}

void queue ::pop()
{
	rear++;
}

void queue :: peek(int &arx, int &ary, int &id)
{
	arx = Arx[rear + 1];
	ary = Ary[rear + 1];
	id = Id[rear + 1];
}

int N;
int arr[21][21];
int gold[21][21]; // dem so luong mo vang co the di duoc neu di tu vi tri do
int street[21][21];
int vs[21][21];

void reset(int a[21][21])
{
	for(int i = 0; i < 21; i++)
	{
		for(int j = 0; j < 21; j++)
		{
			a[i][j] = 0;
		}
	}
}

int dx[] = { -1,  0,  0,  1};
int dy[] = {  0,  1, -1,  0};


// BFS tai cac vi tri co mo vang
void BFS(int x1, int y1)
{
	reset(vs);
	front = rear = -1;
	vs[x1][y1] = 1;
	int id = 0;
	queue qe;
	qe.push(x1, y1, id);
	while(!qe.isEmpty())
	{
		int x, y;
		qe.peek(x, y, id);
		qe.pop();
		for(int i = 0; i < 4; i++)
		{
			int t = x + dx[i];
			int k = y + dy[i];
			if(t >= 0 && t < N && k >= 0 && k < N)
			{
				if(vs[t][k] == 0  && arr[t][k] != 0)
				{
					// neu vi tri chua dc tham va khong phai da thi cho dem vang++ va con duong neu nho hon vt thi cap nhat xa nhat
					gold[t][k]++;
					if(street[t][k] < id + 1)
					{
						street[t][k] = id + 1;
					}
					qe.push(t, k, id + 1);
					vs[t][k] = 1;
				}
			}
		}
	}
}


int main()
{
	//freopen("input.txt", "r", stdin);
	int testcase;
	cin >> testcase;
	for(int tc = 1; tc <= testcase; tc++)
	{
		cin  >> N;
		reset(arr);
		reset(street);
		reset(gold);
		int vtx[5] = {0};
		int vty[5] = {0};
		int K;
		cin >> K;
		for(int i = 0; i < K; i++)
		{
			int x, y;
			cin >> x >> y;
			arr[x - 1][y - 1] = 2;
			vtx[i] = x - 1;
			vty[i] = y - 1;
		}
		for(int i = 0; i < N; i++)
		{
			for(int j = 0; j < N; j++)
			{
				int x;
				cin >> x;
				if(arr[i][j] != 2)
				{
					arr[i][j] = x;
				}
			}
		}
		// BFS tai tung vi tri cua mo vang
		for(int i = 0; i < N; i++)
		{
			for(int j = 0; j < N; j++)
			{
				if(arr[i][j] == 2)
				{
					BFS(i, j);
				}
			}
		}
		// vi co toi da k diem vang 
		// khi xet thi uu tien cho vi tri co nhieu vang nhat
		int min = 10000;
		int x, y;
		for(int i1 = K; i1 >= 1; i1--)
		{
			int dk = 0;
			for(int i = 0; i < N; i++)
			{

				for(int j = 0; j < N; j++)
				{
					if(gold[i][j] == i1 && arr[i][j] != 2)
					{
						if(min > street[i][j])
						{
							dk = 1;
							min = street[i][j];
							x = i;
							y = j;
						}
					}
				}
			}
			if(dk == 1)
			{
				break;
			}
		}
		if(min == 10000)
		{
			cout<<"Case #"<<tc<<endl<<-1<<endl;
		}
		else
		{
			BFS(x, y);
			cout<<"Case #"<<tc<<endl<<min<<endl;
			for(int i = 0; i < K; i++)
			{
				if(vs[vtx[i]][vty[i]] == 0)
				{
					cout<<vtx[i] + 1 <<" "<<vty[i] + 1<<endl;
				}
			}
		}
	}
}