#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
int n;
vector <vector <int> > r;
vector <int> po, pz;
int fpo(int i){
if(po[i]==i){
return i;
}
return po[i]=fpo(po[i]);
}
int fpz(int i){
if(pz[i]==i){
return i;
}
return pz[i]=fpz(pz[i]);
}
int construct(vector <vector <int> > p) {
n=p.size();
r.assign(n, vector <int> (n, 0));
po.resize(n);
pz.resize(n);
for(int i=0; i<n; ++i){
po[i]=i;
pz[i]=i;
}
for(int i=0; i<n; ++i){
if(p[i][i]!=1){
return 0;
}
for(int j=i+1; j<n; ++j){
if(p[i][j]!=p[j][i]){
return 0;
}
if(p[i][j]==1){
po[fpo(i)]=fpo(j);
}
if(p[i][j]){
pz[fpz(i)]=fpz(j);
}
}
}
for(int i=0; i<n; ++i){
for(int j=0; j<n; ++j){
if(fpo(i)==fpo(j) && p[i][j]!=1){
return 0;
}
if(fpz(i)==fpz(j) && p[i][j]==0){
return 0;
}
}
}
for(int i=0; i<n; ++i){
if(fpo(i)!=i){
r[i][po[i]]=1;
r[po[i]][i]=1;
}
}
vector <int> rp;
for(int i=0; i<n; ++i){
if(fpo(i)==i){
rp.push_back(i);
}
}
vector <vector <int> > px(n);
for(int i:rp){
px[fpz(i)].push_back(i);
}
for(int i=0; i<n; ++i){
if(px[i].size()==2){
return 0;
}
if(px[i].size()>1){
int cp;
for(int j=0; j<px[i].size(); ++j){
int x=p[px[i][j]][px[i][(j+1)%(px[i].size())]];
r[px[i][j]][px[i][(j+1)%(px[i].size())]]=1;
r[px[i][(j+1)%(px[i].size())]][px[i][j]]=1;
if(x<2){
return 0;
}
for(int k=0; k<n; ++k){
if(p[px[i][j]][k]>1 && p[px[i][j]][k]!=x){
return 0;
}
}
cp=x;
}
if(cp==3){
if(px[i].size()<4){
return 0;
}
r[px[i][0]][px[i][2]]=1;
r[px[i][2]][px[i][0]]=1;
}
}
}
build(r);
return 1;
}
