#include<bits/stdc++.h>
#include "supertrees.h"
using namespace std;
int n,m,fa[1010],d[1010];
int find(int a){
return fa[a]==a?a:fa[a]=find(fa[a]);
}
int merge(int u,int v){
u=find(u),v=find(v);
if(u==v) return false;
fa[u]=v;return true;
}
struct node{
int id,fa;
bool operator <(const node &b)const{
return fa<b.fa;
}
}c[1010];
int construct(vector<vector<int> >p){
n=p.size();
vector<vector<int> >ans;
for(int i=0;i<n;i++){
vector<int> row;
row.resize(n);
ans.push_back(row);
}
for(int i=0;i<n;i++) fa[i]=i;
for(int i=0;i<n;i++) for(int j=i+1;j<n;j++){
if(p[i][j]>=3) return false;
if(p[i][j]==1) merge(i,j);
}
for(int i=0;i<n;i++) for(int j=i+1;j<n;j++) if(p[i][j]!=p[find(i)][find(j)]) return false;
for(int i=0;i<n;i++) fa[i]=i;
for(int i=0;i<n;i++) for(int j=i+1;j<n;j++){
if(p[i][j]==1){
if(merge(i,j)) ans[i][j]=ans[j][i]=1;
}
}
for(int i=0;i<n;i++) d[i]=find(i),fa[i]=i;
sort(d,d+n);
int sz=unique(d,d+n)-d;
for(int i=0;i<sz;i++){
for(int j=i+1;j<sz;j++){
if(p[d[i]][d[j]]==2) merge(d[i],d[j]);
}
}
for(int i=0;i<sz;i++){
for(int j=i+1;j<sz;j++){
if((p[d[i]][d[j]]==0&&find(d[i])==find(d[j]))||(p[d[i]][d[j]]==2&&find(d[i])!=find(d[j]))) return 0;
}
}
for(int i=0;i<sz;i++) c[i].id=d[i],c[i].fa=find(d[i]);
sort(c,c+sz);
for(int i=0,lst=0;i<sz;i++){
if(i&&c[i].fa==c[i-1].fa) ans[c[i].id][c[i-1].id]=ans[c[i-1].id][c[i].id]=1;
if(i&&c[i].fa!=c[i-1].fa){
if(lst!=i-1) ans[c[i-1].id][c[lst].id]=ans[c[lst].id][c[i-1].id]=1;
if(lst==i-2) return false;
lst=i;
}
if(i==sz-1){
if(lst==i-1) return false;
if(lst!=i) ans[c[i].id][c[lst].id]=ans[c[lst].id][c[i].id]=1;
}
}
build(ans);
return true;
}
