#include <bits/stdc++.h>
#include "supertrees.h"
using namespace std;
vector<int> par(1015),sz(1015,1);
int findPar(int u){
if(par[u]==u) return u;
return par[u]=findPar(par[u]);
}
void unite(int u,int v){
int ulp=findPar(u);
int vlp=findPar(v);
if(ulp==vlp) return;
if(sz[ulp]>sz[vlp]){
par[vlp]=ulp;
sz[ulp]+=sz[vlp];
}else{
par[ulp]=vlp;
sz[vlp]+=sz[ulp];
}
}
bool is_samee(int u,int v){
return findPar(u)==findPar(v);
}
int construct(vector<vector<int>> p) {
int n = p.size();
vector<vector<int>> adj(n,vector<int>(n,0));
for(int i=0;i<n;++i) par[i]=i;
for(int i=0;i<n;++i){
for(int j=i+1;j<n;++j){
if(p[i][j]>0) unite(i,j);
}
}
for(int i=0;i<n;++i){
if(sz[findPar(i)]==2) return 0;
for(int j=i+1;j<n;++j){
if(p[i][j]==0&&is_samee(i,j)){
return 0;
}
}
}
vector<int> last(n+1,-1),first(n+1,-1);
for(int i=0;i<n;++i){
int ulp=findPar(i);
if(last[ulp]!=-1){
adj[i][last[ulp]]=1;
adj[last[ulp]][i]=1;
}
if(first[ulp]==-1) first[ulp]=i;
last[ulp]=i;
}
for(int i=0;i<n;++i){
int ulp=findPar(i);
if(sz[ulp]>1) adj[last[ulp]][first[ulp]]=adj[first[ulp]][last[ulp]]=1;
}
build(adj);
return 1;
}
