#include "supertrees.h"
#include <vector>
using namespace std;
struct DSU{
vector<int>par,sz;
void init(int n){
par.resize(n+1);sz.resize(n+1);
for(int i=0;i<n;i++)par[i]=i,sz[i]=1;
}
int root(int u){
return par[u]==u ? u:par[u]=root(par[u]);
}
bool merge(int u,int v){
int ru=root(u),rv=root(v);
if(ru==rv)return 0;
if(sz[ru]>sz[rv])swap(sz[ru],sz[rv]);
par[ru]=rv;sz[rv]+=sz[ru];
return 1;
}
};
int construct(std::vector<std::vector<int>> p) {
int n=p[0].size();
vector<vector<int>>v(n,vector<int>(n,0));
DSU d1;d1.init(n);
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
if(p[i][j]==0)continue;
d1.merge(i,j);
}
}
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(p[i][j]==0&&d1.root(i)==d1.root(j))return 0;
}
}
vector<vector<int>>comp(n);
for(int i=0;i<n;i++){
comp[d1.root(i)].push_back(i);
}
for(int i=0;i<n;i++){
if(comp[i].size()){
bool valid=0;
for(int j=0;j<comp[i].size();j++){
for(int k=0;k<comp[i].size();k++){
if(p[comp[i][j]][comp[i][k]]==2){valid=1;break;}
}
if(valid)break;
}
if(valid){
if(comp[i].size()<3)return 0;
for(int j=0;j<comp[i].size();j++){
int u=comp[i][j],v1=comp[i][(j+1)%(comp[i].size())];
v[u][v1]=1;v[v1][u]=1;
}
for(int j=0;j<comp[i].size();j++){
for(int k=0;k<comp[i].size();k++){
if(p[comp[i][j]][comp[i][k]]!=2){return 0;}
}
}
}
else {
for(int j=1;j<comp[i].size();j++){
int u=comp[i][j],v1=comp[i][j-1];
v[u][v1]=1;v[v1][u]=1;
}
}
}
}
build(v);
return 1;
}
