#include "supertrees.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int construct(vector <vector <int>> p) {
int n = p[0].size();
for (auto &E : p) for (auto &e : E) if (e == 3) return 0;
int par1[n]; iota(par1, par1+n, 0);
function <int(int)> fi1 = [&] (int x) {
if (x == par1[x]) return x;
return par1[x] = fi1(par1[x]);
};
for (int u = 0; u < n; u++) {
for (int v = 0; v < n; v++) if (v != u) {
if (p[u][v]) par1[fi1(v)] = fi1(u);
}
}
for (int u = 0; u < n; u++) {
for (int v = 0; v < n; v++) if (v != u) {
if (p[u][v] && fi1(u) != fi1(v)) return 0;
if (!p[u][v] && fi1(u) == fi1(v)) return 0;
}
}
int par2[n]; iota(par2, par2+n, 0);
function <int(int)> fi2 = [&] (int x) {
if (x == par2[x]) return x;
return par2[x] = fi2(par2[x]);
};
vector <vector <int>> E(n, vector <int>(n));
for (int u = 0; u < n; u++) {
for (int v = 0; v < n; v++) if (v != u) {
if (p[u][v] == 1 && fi2(u) != fi2(v)) par2[fi2(v)] = fi2(u), E[u][v] = E[v][u] = 1;
}
}
for (int u = 0; u < n; u++) {
for (int v = 0; v < n; v++) if (v != u) {
if (p[u][v] == 1 && fi2(u) != fi2(v)) return 0;
if (p[u][v] != 1 && fi2(u) == fi2(v)) return 0;
}
}
set <int> st[n];
for (int u = 0; u < n; u++) st[fi1(u)].emplace(fi2(u));
for (auto &e : st) if (e.size() > 1) {
if ((int) e.size() == 2) return 0;
vector <int> v;
for (auto &x : e) v.emplace_back(x);
int l = v.size();
for (int i = 0; i < l; i++) {
int p = v[i], q = v[(i+1)%l];
E[p][q] = E[q][p] = 1;
}
}
build(E);
return 1;
}
