#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) x.begin(), x.end()
#define mp make_pair
#define mt make_tuple
#define x first
#define y second
#include "supertrees.h"
namespace my {
const int N = 1010;
int n, g[N][N], res[N][N];
void edge(int v, int u) {
res[v][u] = true;
res[u][v] = true;
}
vector<int> get_comp(int v, int msk) {
static int lst[N], timer = 0;
++timer;
lst[v] = timer;
queue<int> q;
vector<int> ret;
q.push(v);
while (q.size()) {
v = q.front(); q.pop();
ret.push_back(v);
for (int u = 0; u < n; ++u) {
if (lst[u] == timer) {
continue;
}
if ((msk >> g[v][u]) & 1) {
lst[u] = timer;
q.push(u);
}
}
}
return ret;
}
bool u1[N], u12[N];
}
int construct(vector<vector<int>> _g) {
using namespace my;
n = (int)_g.size();
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
g[i][j] = _g[i][j];
if (g[i][j] == 3) {
return 0;
}
}
}
for (int i = 0; i < n; ++i) {
if (u12[i]) {
continue;
}
vector<int> c12 = get_comp(i, (1 << 1) | (1 << 2));
// cout << "! " << c12.size() << endl;
vector<int> cycle;
for (int v : c12) {
u12[v] = true;
if (u1[v]) {
continue;
}
vector<int> c1 = get_comp(v, 1 << 1);
// cout << "? " << c1.size() << " " << c1[0] << endl;
for (int u : c1) {
for (int uu : c1) {
if (g[u][uu] != 1) {
return 0;
}
}
u1[u] = true;
}
for (int u : c1) {
for (int uu : c12) {
if (u1[uu]) {
continue;
}
if (g[u][uu] != 2) {
return 0;
}
}
}
for (int idx = 0; idx + 1 < (int)c1.size(); ++idx) {
edge(c1[idx], c1[idx + 1]);
}
cycle.push_back(c1.front());
}
if (cycle.size() == 1) {
continue;
}
for (int idx = 0; idx < (int)cycle.size(); ++idx) {
edge(cycle[idx], cycle[(idx + 1) % cycle.size()]);
}
}
vector<vector<int>> answer;
for (int i = 0; i < n; ++i) {
answer.push_back(vector<int>(res[i], res[i] + n));
}
build(answer);
return 1;
}
#ifdef LC
#include "grader.cpp"
#endif
