#include "supertrees.h"
#include <vector>
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
vector<int> g[1005];
bool vs[1005],y;
int dad[1005],ran[1005];
bool VS[1005];
int bus(int u)
{
if (dad[u] != u) dad[u] = bus(dad[u]);
return dad[u];
}
void unir(int u,int v)
{
u = bus(u); v = bus(v);
if (u != v) {
if (ran[u]>ran[v]) dad[v] = u;
else if (ran[v] > ran[u]) dad[u] = v;
else {
ran[u]++;
dad[v] = u;
}
}
}
int construct(std::vector<std::vector<int>> p) {
int n = p.size();
std::vector<std::vector<int>> answer;
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++) {
dad[i] = i;
}
y= true;
for (int i=0;i<n;i++) if (!VS[i]) {
for (int j=0;j<n;j++) if (i != j) {
if (p[i][j]==1) {
if (bus(i) != bus(j)) {
answer[i][j] = 1;
answer[j][i] = 1;
VS[j] = true;
unir(i,j);
}
}
}
}
for (int i=0;i<n;i++) VS[i] = false;
for (int i=0;i<n;i++) if (!VS[i]) {
set<int> s ;
s.clear();
s.insert(bus(i));
for (int j=0;j<n;j++) if (p[i][j]==2) {
VS[j] = true;
s.insert(bus(j));
}
vector<int> x ;
x.clear();
for (int u : s) x.pb(u);
int xx = x.size();
if (xx<3) {
} else {
for (int j=0;j<xx-1;j++) {
answer[bus(x[j])][bus(x[j+1])] = 1;
answer[bus(x[j+1])][bus(x[j])] = 1;
}
answer[bus(x[0])][bus(x[xx-1])] = 1;
answer[bus(x[xx-1])][bus(x[0])] = 1;
}
}
if (y) build(answer);
if (y) return 1;
else return 0;
}
