#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
const int nax = 1000;
int par[nax], sz[nax];
vector<int>L[nax];
int find(int v) {
return par[v] = (v == par[v]) ? v : find(par[v]);
}
void unite(int u, int v) {
u = find(u), v = find(v);
if(u==v) return;
if(sz[u] < sz[v]) swap(u, v);
for(int x : L[v]) {
L[u].push_back(x);
}
sz[u] += sz[v];
par[v] = u;
}
int construct(vector<vector<int>> p) {
int n = p.size();
for(int i=0; i<n; ++i) {
par[i] = i, sz[i] = 1;
L[i] = {i};
}
for(int i=0; i<n; ++i) {
for(int j=0; j<n; ++j) if(p[i][j]) {
unite(i, j);
}
}
for(int i=0; i<n; ++i) {
for(int j=0; j<n; ++j) if(!p[i][j]) {
if(find(i) == find(j)) return 0;
}
}
vector<vector<int>>ans(n, vector<int>(n));
for(int i=0; i<n; ++i) if(i==find(i)) {
if(sz[i]>1) {
for(int x=0; x+1<sz[i]; ++x) {
ans[L[i][x]][L[i][x+1]] = ans[L[i][x+1]][L[i][x]] = 1;
}
if(p[i][L[i][1]]==2) {
if(sz[i]<=2) return 0;
for(int x=0; x<sz[i]; ++x) {
for(int y=x+1; y<sz[i]; ++y) {
if(p[L[i][x]][L[i][y]]!=2) {
return 0;
}
}
}
ans[L[i][0]][L[i][sz[i]-1]] = ans[L[i][sz[i]-1]][L[i][0]] = 1;
}
}
}
build(ans);
return 1;
}
