#include <bits/stdc++.h>
#include "grid_encoding.h"
using namespace std;

const int N = 500;

void send(vector <vector <int> > A) {
	int n = A.size();
	vector <int> x(n), y(n), cnt(n);
	for (int i = 0; i < n; ++i) {
		x[i] = i;
		for (int j = 0; j < n; ++j) {
			cnt[i] += A[i][j];
		}
	}
	for (int i = 0; i < n; ++i) {
		for (int j = i + 1; j < n; ++j) {
			if (cnt[i] > cnt[j]) {
				swap(x[i], x[j]);
				swap(cnt[i], cnt[j]);
				swap(A[i], A[j]);
			}
		}
	}
	for (int i = 0; i < n; ++i) {
		y[i] = i;
		cnt[i] = 0;
		for (int j = 0; j < n; ++j) {
			cnt[i] += A[j][i];
		}
	}
	for (int i = 0; i < n; ++i) {
		for (int j = i + 1; j < n; ++j) {
			if (cnt[i] > cnt[j]) {
				swap(y[i], y[j]);
				swap(cnt[i], cnt[j]);
				for (int p = 0; p < n; ++p) {
					swap(A[p][i], A[p][j]);
				}
			}
		}
	}
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			if (A[j][i] == 1) {
				select(x[j], y[i]);
				break;
			}
		}
	}
	for (int i = 0; i < n - 1; ++i) {
		for (int j = 0; j < n; ++j) {
			if (!A[i][j] && (j == n - 1 || A[i][j + 1])) {
				select(x[i], y[j]);
			}
		}
	}
}

vector <vector <int> > reconstruct(vector <vector <int> > A) {
	int n = A.size();
	vector <int> pre(n), x(n), cnt(n);
	for (int i = 0; i < n; ++i) {
		x[i] = i;
		for (int j = 0; j < n; ++j) {
			if (A[i][j] != -1) {
				++cnt[i];
			}
		}
	}
	bitset <N> vis[N];
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			for (int p = 0; p < n; ++p) {
				if ((A[i][p] == 0 && A[j][p] == 1) || (A[i][p] == 0 && A[j][p] == 0 && cnt[i] > cnt[j])) {
					vis[i][j] = 1;
				}
			}
		}
	}
	for (int i = 0; i < n; ++i) {
		if (cnt[i] == 0) {
			for (int j = 0; j < n; ++j) {
				if (j != i) {
					vis[j][i] = 1;
				}
			}
		}
	}
	for (int p = 0; p < n; ++p) {
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < n; ++j) {
				if (vis[i][p] && vis[p][j]) {
					vis[i][j] = 1;
				}
			}
		}
	}
	for (int i = 0; i < n; ++i) {
		for (int j = i + 1; j < n; ++j) {
			if (vis[x[j]][x[i]]) {
				swap(x[i], x[j]);
				swap(A[i], A[j]);
			}
		}
	}
	for (int i = 0; i < n; ++i) {
		bool flg = 0;
		for (int j = 0; j < n; ++j) {
			if (A[j][i] == 1) {
				flg = 1;
			}
			A[j][i] = flg;
		}
	}
	vector <vector <int> > res(n);
	for (int i = 0; i < n; ++i) {
		res[i].resize(n);
	}
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			res[x[i]][j] = A[i][j];
		}
	}
	return res;
}