#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1<<12;
int n;
vector<vector<int>> res;
struct dsu {
vector<int> c[maxn];
int p[maxn];
dsu(int n = 0) {
for(int i = 0; i < n; i++) {
p[i] = i;
c[i].push_back(i);
}
}
int par(int a) {
if(p[a] == a) return a;
return a = par(p[a]);
}
void unite(int i, int j) {
i = par(i), j = par(j);
if(i == j) return;
if(c[i].size() < c[j].size()) swap(i, j);
for(auto x : c[j]) c[i].push_back(x);
p[j] = i;
}
};
int construct(std::vector<std::vector<int>> p) {
for(auto i : p) for(auto j : i) if(j == 3) return 0;
n = p.size();
res.resize(n, vector<int>(n, 0));
dsu c1(n), c2(n);
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
if(p[i][j] == 1) c1.unite(i, j);
for(int i = 0; i< n; i++)
for(int j = 0; j < n; j++) {
int x = c1.par(i), y = c1.par(j);
if(p[i][j] != p[x][y]) return 0;
}
for(int i = 0; i < n; i++) if(c1.par(i) == i)
for(int j = 0; j < n; j++) if(c1.par(j) == j) {
if(p[i][j] == 2) {
c2.unite(i, j);
}
}
for(int i = 0; i < n; i++) {
if(c1.par(i) == i) {
int lst = -1;
for(auto x : c1.c[i]) {
if(lst != -1) res[lst][x] = 1;
lst = x;
}
}
if(c2.par(i) == i) {
if(c2.c[i].size() == 1) continue;
if(c2.c[i].size() == 2) return 0;
for(auto x : c2.c[i])
for(auto y : c2.c[i])
if(p[x][y] != 2 && x != y) return 0;
int lst = -1;
c2.c[i].push_back(c2.c[i][0]);
for(auto x : c2.c[i]) {
if(lst != -1) res[lst][x] = 1;
lst = x;
}
}
}
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++) if(res[i][j] == 1) res[j][i] = 1;
build(res);
return 1;
}
