#include <bits/stdc++.h>
#include "supertrees.h"
using namespace std;
struct dsu {
vector<int> p, sz;
dsu(int n) {
p.resize(n);
iota(p.begin(), p.end(), 0);
sz.resize(n, 1);
};
int f (int x) {
return (p[x] == x? x: p[x] = f(p[x]));
};
int unin(int x, int y) {
x = f(x); y = f(y);
if(x == y) return 0;
if(sz[x] < sz[y]) swap(x, y);
sz[x] += sz[y];
p[y] = x;
return 1;
};
};
int construct(vector<vector<int>> p) {
int n = p.size();
vector<vector<int>> ans(n, vector<int> (n));
dsu t(n);
auto ad = [&](int x, int y) {
ans[x][y] = 1;
ans[y][x] = 1;
t.unin(x, y);
};
for(int i = 0; i < n; i ++ ) {
for(int j = 0; j < n; j ++ ) {
if(p[i][j] == 1 && t.unin(i, j)) ad(i, j);
if(p[i][j] == 3) return 0;
};
};
{vector<int> ch(n);
for(int i = 0; i < n; i ++ ) {
if(ch[t.f(i)])continue;
vector<int> vs(n), al;
queue<int> q;
for(int j = 0; j < n; j ++ ) {
if(t.f(i) != t.f(j) && p[i][j] == 2) {
q.push(t.f(i));
vs[t.f(i)] = 1;
break;
};
};
while(q.size()) {
auto ps = q.front();
q.pop();
al.push_back(ps);
ch[ps] = 1;
for(int j = 0; j < n; j ++ ) {
if(vs[t.f(j)]) continue;
if(ps != t.f(j) && p[ps][j] == 2) {
q.push(t.f(j));
vs[t.f(j)] = 1;
};
};
};
if(al.size() > 1 && al.size() <= 2) return 0;
for(int j = 0; j < (int)al.size(); j ++ ) ad(al[j], al[(j+1) %al.size()]);
};
};
for(int i = 0; i < n; i ++ ) {
for(int j = 0; j < n; j ++ ) {
if(t.f(i) == t.f(j) && p[i][j] == 0) return 0;
};
};
build(ans);
return 1;
}
