#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3+5;
int n ;
int a[N][N];
int dad[N];
bool vs[N];
bool act[N];
struct UnionFind {
int ran;
int da;
};
UnionFind uf[N];
vector<std::vector<int>> answer;
vector<int> g[N];
int bus(int u)
{
if (uf[u].da != u) uf[u].da = bus(uf[u].da);
return uf[u].da;
}
void unir(int u,int v)
{
u = bus(u);
v = bus(v);
if (u != v) {
if (uf[u].ran > uf[v].ran) uf[v].da = u;
else if (uf[u].ran < uf[v].ran) uf[u].da = v;
else {
uf[u].ran++;
uf[v].da = u;
}
}
return;
}
int construct(std::vector<std::vector<int>> _p) {
n = _p.size();
for (int i = 0; i < n; i++) {
std::vector<int> row;
row.resize(n);
answer.push_back(row);
}
for (int i=0;i<n;i++) for (int j=0;j<n;j++) a[i][j] = _p[i][j];
for (int i=0;i<n;i++) for (int j=0;j<n;j++) if (a[i][j] > 2)
return 0;
for (int i=0;i<n;i++) {
uf[i].ran = 0;
uf[i].da = i;
}
for (int i=0;i<n;i++) for (int j=0;j<n;j++) if (a[i][j]>0) unir(i,j);
for (int i=0;i<n;i++) for (int j=0;j<n;j++) if (a[i][j] == 0) if (bus(i) == bus(j)) {
return 0;
}
for (int i=0;i<n;i++) g[bus(i)].push_back(i);
for (int i=0;i<n;i++) {
for (int j=0;j<(int)g[i].size();j++) act[g[i][j]] = true;
for (int j=0;j<(int)g[i].size();j++) {
int x = g[i][j];
for (int k=0;k<(int)g[i].size() && act[x];k++) {
int y = g[i][k];
if (x != y) {
if (a[x][y] == 1) {
if (act[y]) {
act[x] = false;
dad[x] = y;
} else if (dad[y] != x) {
dad[x] = dad[y];
act[x] = false;
}
}
}
}
}
vector<int> gg;
for (int j=0;j<(int)g[i].size();j++) if (act[g[i][j]]) gg.push_back(g[i][j]);
for (int j=1;j<(int)gg.size();j++) {
answer[gg[j]][gg[j-1]] = answer[gg[j-1]][gg[j]] = 1;
}
int pp = gg.size();
if (pp>1) answer[gg[0]][gg[pp-1]] = answer[gg[pp-1]][gg[0]] = 1;
for (int j=0;j<(int)g[i].size();j++) if (!act[g[i][j]]) {
int x = g[i][j];
answer[x][dad[x]] = answer[dad[x]][x] = 1;
}
}
build(answer);
return 1;
}
