#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
struct DSU {
int n;
vector<int> sz, p;
DSU(int _n) {
n = _n;
sz.assign(n, 1);
p.resize(n);
iota(p.begin(), p.end(), 0);
}
int pr(int v) {
if (p[v] == v) {
return v;
}
return p[v] = pr(p[v]);
}
void unite(int a, int b) {
a = pr(a), b = pr(b);
if (a == b) {
return;
}
if (sz[a] < sz[b]) {
swap(a, b);
}
p[b] = a;
sz[a] += sz[b];
}
};
int construct(vector<vector<int>> p) {
int n = p.size();
vector<vector<int>> answer(n, vector<int>(n));
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
if (p[i][j] == 3) {
return 0;
}
}
}
DSU d0(n);
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
if (p[i][j] != 0) {
d0.unite(i, j);
}
}
}
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
if (d0.pr(i) == d0.pr(j) && p[i][j] == 0) {
return 0;
}
}
}
DSU d1(n);
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
if (p[i][j] == 1) {
d1.unite(i, j);
}
}
}
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
if (d1.pr(i) == d1.pr(j) && p[i][j] != 1) {
return 0;
}
}
if (d1.pr(i) != i) {
answer[d1.pr(i)][i] = answer[i][d1.pr(i)] = 1;
}
}
DSU d2(n);
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
if (p[i][j] == 2) {
d2.unite(i, j);
}
}
}
vector<vector<int>> cycles(n);
for (int i = 0; i < n; ++i) {
if (d2.sz[d2.pr(i)] != 1 && i == d1.pr(i)) {
cycles[d2.pr(i)].push_back(i);
}
}
for (int i = 0; i < n; ++i) {
if (cycles[i].size() == 2) {
return 0;
}
for (int j = 0; j < (int)cycles[i].size(); ++j) {
int nxt = j + 1;
if (nxt == (int)cycles[i].size()) {
nxt = 0;
}
answer[cycles[i][j]][cycles[i][nxt]] = answer[cycles[i][nxt]][cycles[i][j]] = 1;
}
}
build(answer);
return 1;
}
