#include "supertrees.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
typedef long long ll;
using namespace std;
vector<vector<int>> ans;
int n;
struct dsu {
vector<int> par;
vector<vector<int>> nds;
void init(int n) {
par.assign(n, -1);
nds.assign(n, vector<int>());
Loop (i,0,n)
nds[i].push_back(i);
}
int rt(int v) { return par[v] == -1? v: (par[v] = rt(par[v])); }
bool same(int v, int u) { return rt(v) == rt(u); }
bool unite(int v, int u) {
v = rt(v);
u = rt(u);
if (v == u)
return 0;
if (nds[v].size() < nds[u].size())
swap(v, u);
par[u] = v;
nds[v].insert(nds[v].end(), nds[u].begin(), nds[u].end());
vector<int> tmp;
tmp.swap(nds[u]);
return 1;
}
};
int construct(std::vector<std::vector<int>> p) {
n = p.size();
ans.assign(n, vector<int>(n, 0));
Loop (i,0,n) Loop (j,i+1,n) {
if (p[i][j] == 3)
return 0;
}
dsu dsu1;
dsu1.init(n);
Loop (i,0,n) Loop (j,i+1,n) {
if (p[i][j] == 1 && dsu1.unite(i, j))
ans[i][j] = ans[j][i] = 1;
}
Loop (i,0,n) Loop (j,i+1,n) {
if (p[i][j] != 1 && dsu1.same(i, j))
return 0;
}
dsu dsu2;
dsu2.init(n);
Loop (i,0,n) Loop (j,i+1,n) {
if (p[i][j] != 2)
continue;
if (dsu1.same(i, j))
return 0;
int x = dsu1.rt(i);
int y = dsu1.rt(j);
dsu2.unite(x, y);
}
Loop (i,0,n) Loop (j,i+1,n) {
int x = dsu1.rt(i);
int y = dsu1.rt(j);
if (p[i][j] == 0 && dsu2.same(x, y))
return 0;
}
Loop (i,0,n) {
if (dsu2.par[i] != -1)
continue;
int sz = dsu2.nds[i].size();
if (sz <= 1)
continue;
Loop (j,0,sz) {
int x = dsu2.nds[i][j];
int y = dsu2.nds[i][(j+1)%sz];
ans[x][y] = ans[y][x] = 1;
}
}
build(ans);
return 1;
}
