#include "bits/stdc++.h"
#include "supertrees.h"
using namespace std;
#define for_(i, s, e) for (int i = s; i < (int) e; i++)
#define for__(i, s, e) for (ll i = s; i < e; i++)
typedef long long ll;
typedef vector<int> vi;
typedef array<int, 2> ii;
// #define endl '\n'
bool valid = true;
vi singleComp;
vector<vi> answer, paths, doubleAdj, compEl; // da: -1: dunno, 0: nope, 1: yep
int n;
void dfs(int p, vi &comp, vector<vi> &adj) {
compEl[comp[p]].push_back(p);
for_(i, 0, n) if (p != i and adj[p][i] == 1) {
if (comp[i] == -1) {
comp[i] = comp[p];
dfs(i, comp, adj);
}
if (comp[i] != comp[p]) valid = false;
}
}
bool checkDouble(int a, int b) {
for (auto x: compEl[a]) for (auto y: compEl[b]) if (paths[x][y] != 2) return false;
return true;
}
int construct(vector<vi> p) {
paths = p;
n = paths.size();
answer.resize(n, vi(n)); singleComp.resize(n, -1); doubleAdj.resize(n, vi(n, -1)); compEl.resize(n);
for_(i, 0, n) if (singleComp[i] == -1) {
singleComp[i] = i;
dfs(i, singleComp, paths);
}
for_(i, 0, n) for_(j, i+1, n) if (paths[i][j] == 2) {
if (singleComp[i] == singleComp[j]) {
valid = false;
continue;
}
int a = singleComp[i], b = singleComp[j];
if (doubleAdj[a][b] == -1) {
doubleAdj[a][b] = doubleAdj[b][a] = checkDouble(a, b);
if (!doubleAdj[a][b]) valid = false;
}
}
compEl.assign(n, {});
vi doubleComp(n, -1);
for_(i, 0, n) if (singleComp[i] == i and doubleComp[i] == -1) {
doubleComp[i] = i;
dfs(i, doubleComp, doubleAdj);
}
for_(i, 0, n) if (compEl[i].size() == 2) valid = false;
for_(i, 0, n) for_(j, i+1, n) {
if (singleComp[i] != singleComp[j] and (paths[i][j] == 2 or doubleComp[singleComp[i]] == doubleComp[singleComp[j]])) {
valid = valid and paths[i][j] == 2 and doubleComp[singleComp[i]] == doubleComp[singleComp[j]];
}
if (paths[i][j] == 0) valid = valid and singleComp[i] != singleComp[j] and doubleComp[singleComp[i]] != doubleComp[singleComp[j]];
else if (paths[i][j] == 1) valid = valid and singleComp[i] == singleComp[j];
else if (paths[i][j] == 2) valid = valid and singleComp[i] != singleComp[j] and doubleComp[singleComp[i]] == doubleComp[singleComp[j]];
else valid = false;
}
for_(i, 0, n) for_(j, i+1, n) if (singleComp[i] == i and singleComp[j] == j and doubleComp[i] == doubleComp[j]) valid = valid and checkDouble(i, j);
if (!valid) return 0;
for_(i, 0, n) if (singleComp[i] != i) answer[i][singleComp[i]] = answer[singleComp[i]][i] = 1;
for_(i, 0, n) if (compEl[i].size() > 1) {
int s = compEl[i].size();
for_(j, 0, s) {
int nxt = j == s-1 ? 0 : j+1;
answer[compEl[i][j]][compEl[i][nxt]] = answer[compEl[i][nxt]][compEl[i][j]] = 1;
}
}
build(answer);
return 1;
}
