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

	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;
		reset3();

		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 && arr[i][j] != 2) {
						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;
		}*/
	}
}

/*#include <iostream>
#define MIN 999999999
using namespace std;

int n, g;
int r, c;
int arr[21][21];
int visited1[21][21];
int len1[21][21];
int dR[4] = { -1, 0, 1, 0 };
int dC[4] = { 0, 1, 0, -1 };
int visitedV[11];

typedef struct Point {
	int x, y;
};

Point V[21];

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 Q1;

void BFS(Point S) {
	init(Q1);
	push(Q1, S);
	visited1[S.x][S.y] = 1;
	len1[S.x][S.y] = 0;

	while (!empty(Q1)) {
		Point P;
		P = top(Q1);
		pop(Q1);

		for (int k = 0; k < 4; k++) {
			int x = P.x + dR[k];
			int y = P.y + dC[k];

			if (x >= 1 && x <= n && y >= 1 && y <= n && visited1[x][y] == 0 && arr[x][y] != 0) {
				visited1[x][y] = 1;
				len1[x][y] = len1[P.x][P.y] + 1;

				Point P1;
				P1.x = x;
				P1.y = y;
				push(Q1, P1);
			}

		}

	}

}

void resetKT() {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			visited1[i][j] = 0;
			len1[i][j] = 0;
			arr[i][j] = 0;
		}
	}
}

void reset() {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			visited1[i][j] = 0;
			len1[i][j] = 0;
		}
	}
}

void resetIndex() {
	for (int i = 1; i <= g; i++) {
		visitedV[i] = 0;
	}
}

void input() {

	cin >> n >> g;
	resetKT();

	for (int i = 1; i <= g; i++) {
		cin >> r >> c;
		V[i].x = r;
		V[i].y = c;
		arr[r][c] = 1;
	}

	int m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> m;
			arr[i][j] += m;
		}
	}
}

int main() {
	//freopen("vao.txt", "r", stdin);
	int t;
	cin >> t;
	for (int tc = 1; tc <= t; tc++) {

		input();

		int MinTG = MIN;
		int MaxV = -1;

		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (arr[i][j] == 1) {

					reset();
					Point P;
					P.x = i;
					P.y = j;

					BFS(P);

					cout << endl;
					for (int l = 1; l <= n; l++) {
						for (int r = 1; r <= n; r++) {
							cout << len1[l][r] << " ";
						}
						cout << endl;
					}
					cout << endl;

					int countV = 0;
					int MaxTG = -1;
					int arrV[10];
					int index = 1;

					for (int z = 1; z <= g; z++) {
						int xG = V[z].x;
						int yG = V[z].y;
						if (visited1[xG][yG] == 1) {
							arrV[index++] = z;
							countV++;
							MaxTG = max(MaxTG, len1[xG][yG]);

						}
					}
					
					if (MaxTG == 1) {
						cout << i << " " << j << endl;
						i = n + 1;
						j = n+1;
					}

					if (countV > MaxV) {
						resetIndex();

						for (int k = 1; k < index; k++)
							visitedV[arrV[k]] = 1;

						MaxV = countV;
						MinTG = MaxTG;
					}

					else if (countV == MaxV) {
						if (MinTG > MaxTG) {
							resetIndex();

							for (int k = 1; k < index; k++)
								visitedV[arrV[k]] = 1;

							MaxV = countV;
							MinTG = MaxTG;
						}
					}

				}
			}
		}
		cout << "Case #" << tc << endl;

		if (MinTG == MIN) {
			cout << "-1" << endl;
		}
		else {
			if (MinTG == -1) {
				cout << "-1" << endl;
			}
			else {
				cout << MinTG << endl;

				if (MaxV != g) {
					for (int i = 1; i <= g; i++) {
						if (visitedV[i] == 0)
							cout << V[i].x << " " << V[i].y << endl;
					}
				}
			}
		}
	}
	return 0;
}*/