Untitled

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