#include "supertrees.h"
#include <vector>
struct dsu{
int fa[1005];
void init(int n){
for(int i=0;i<n;++i)fa[i]=i;
}
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
void merge(int x,int y){fa[find(x)]=find(y);}
int rt(int x){return fa[x]==x;}
}a,b;
int query(int x,int y){
if(a.find(x)==a.find(y))return 1;
if(b.find(a.find(x))==b.find(a.find(y)))return 2;
return 0;
}
std::vector<int> al[1005],bl[1005];
int construct(std::vector<std::vector<int>> p) {
int n = p.size();
a.init(n);b.init(n);
std::vector<std::vector<int>> ans(n,std::vector<int>(n));
for(int i=0;i<n;++i)for(int j=0;j<n;++j)if(p[i][j]==3)return 0;
for(int i=0;i<n;++i)for(int j=i+1;j<n;++j)if(p[i][j]==1){a.merge(i,j);}
for(int i=0;i<n;++i)for(int j=i+1;j<n;++j)if(p[i][j]==2){b.merge(a.find(i),a.find(j));}
for(int i=0;i<n;++i)for(int j=1;j<n;++j){
if(p[i][j]!=query(i,j))return 0;
}
for(int i=0;i<n;++i){
al[a.find(i)].emplace_back(i);
if(a.rt(i)){
bl[b.find(i)].emplace_back(i);
}
}
for(int i=0;i<n;++i)if(a.rt(i)){
int m=al[i].size();
for(int j=0;j+1<m;++j){
int x=al[i][j],y=al[i][j+1];
ans[x][y]=ans[y][x]=1;
}
}
for(int i=0;i<n;++i){
if(a.rt(i) && b.rt(i)){
if(bl[i].size()==1)continue;
if(bl[i].size()==2)return 0;
int m=bl[i].size();
for(int j=0;j<m;++j){
int x=bl[i][j],y=j==m-1?bl[i][0]:bl[i][j+1];
ans[x][y]=ans[y][x]=1;
}
}
}
build(ans);
return 1;
}
