#include "bits/stdc++.h"
#include "supertrees.h"
#define sz(x) (int)size(x)
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const char nl = '\n';
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
struct dsu {
vector<int> e;
dsu(int n) : e(n, -1) {}
int find(int v) { return e[v] < 0 ? v : e[v] = find(e[v]); }
bool same(int a, int b) { return find(a) == find(b); }
void une(int a, int b) {
a = find(a), b = find(b);
if (a == b) return;
if (e[a] < e[b]) swap(a, b);
e[b] += e[a];
e[a] = b;
}
};
int construct(vector<vector<int>> p) {
int n = sz(p);
vector ans(n, vector<int>(n));
bool f = true;
auto merge1 = [&](vector<int> v) -> void {
for (int i = 0; i < sz(v) - 1; i++) {
int a = v[i];
int b = v[i + 1];
if (a == b) continue;
if (p[a][b] != 1) f = false;
ans[a][b] = 1;
ans[b][a] = 1;
}
};
auto merge2 = [&](vector<int> v) -> void {
for (int i = 0; i < sz(v); i++) {
int a = v[i];
int b = v[(i + 1) % (sz(v))];
if (a == b) continue;
if (p[a][b] != 2) f = false;
ans[a][b] = 1;
ans[b][a] = 1;
}
};
dsu dsu1(n);
for (int i = 0; i < n; i++)
for (int j = i; j < n; j++)
if (p[i][j] == 1)
dsu1.une(i, j);
vector<vector<int>> comp1(n);
for (int i = 0; i < n; i++) {
int p = dsu1.find(i);
comp1[p].push_back(i);
}
for (int i = 0; i < n; i++)
merge1(comp1[i]);
dsu dsu2(n);
for (int i = 0; i < n; i++)
for (int j = i; j < n; j++)
if (p[i][j] == 2) {
int a = dsu1.find(i);
int b = dsu1.find(j);
dsu2.une(a, b);
}
vector<vector<int>> comp2(n);
for (int i = 0; i < n; i++) {
int p = dsu2.find(i);
comp2[p].push_back(i);
}
for (int i = 0; i < n; i++)
merge2(comp2[i]);
// checks
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) {
if (i == j) continue;
if (dsu1.same(i, j)) continue;
int a = dsu1.find(i);
int b = dsu2.find(j);
if (p[i][j] != 2 && dsu2.same(a, b))
return 0;
}
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) {
if (i == j) continue;
int a = dsu1.find(i);
int b = dsu1.find(j);
if (p[i][j] == 0 && (dsu1.same(i, j) || dsu2.same(a, b)))
return 0;
}
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) {
if (i == j) continue;
if (p[i][j] == 1 && !dsu1.same(i, j))
return 0;
}
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) {
if (i == j) continue;
int a = dsu1.find(i);
int b = dsu1.find(j);
if (p[i][j] == 2 && !dsu2.same(a, b))
return 0;
}
if (!f) return 0;
build(ans);
return 1;
}
