#include<bits/stdc++.h>
#include "supertrees.h"
#include <vector>
using namespace std;
int a,b,c,d,e,i,j,ii,jj,zx,xc,f[1009][1009],msh[1009],zm[1009],bo[1009][1009],p[1009],pi,MSH[1009],ZM[1009];
vector <int> v[1009],V[1009];
vector <vector <int> > ANS;
int fnd(int q){
if(msh[q]==0) return q; else return msh[q]=fnd(msh[q]);
}
void mrg(int q, int w){
q=fnd(q);w=fnd(w);
if(q==w) return;
if(zm[q]<zm[w]) swap(q,w);
msh[w]=q;
if(zm[q]==zm[w]) zm[q]++;
}
int FND(int q){
if(MSH[q]==0) return q; else return MSH[q]=fnd(MSH[q]);
}
void MRG(int q, int w){
q=FND(q);w=FND(w);
if(q==w) return;
if(ZM[q]<ZM[w]) swap(q,w);
MSH[w]=q;
if(ZM[q]==ZM[w]) ZM[q]++;
}
int construct(vector <vector <int> > Pp) {
a=Pp.size();
for(i=1; i<=a; i++){
for(j=1; j<=a; j++){
f[i][j]=Pp[i-1][j-1];
if(f[i][j]==3) return 0;
}
}
//check
for(i=1; i<=a; i++){
for(j=i+1; j<=a; j++){
if(f[i][j]!=0) mrg(i,j);
}
}
for(i=1; i<=a; i++){
for(j=i+1; j<=a; j++){
if(fnd(i)==fnd(j)){
if(f[i][j]==0) return 0;
}
}
}
for(i=0; i<=a+1; i++){
msh[i]=zm[i]=0;
}
//
for(i=1; i<=a; i++){
for(j=i+1; j<=a; j++){
if(f[i][j]==1) mrg(i,j);
}
}
for(i=1; i<=a; i++){
v[fnd(i)].push_back(i);
}
for(i=1; i<=a; i++){
for(ii=0; ii<v[i].size(); ii++){
for(jj=ii+1; jj<v[i].size(); jj++){
c=v[i][ii];d=v[i][jj];
if(f[c][d]!=1) return 0;
}
}
}
for(i=1; i<=a; i++){
if(v[i].size()==0) continue;
for(jj=1; jj<v[i].size(); jj++){
c=v[i][jj-1];d=v[i][jj];
bo[c][d]=bo[d][c]=1;
}
pi++;p[pi]=v[i][0];
}
for(i=1; i<=pi; i++){
for(j=i+1; j<=pi; j++){
if(f[p[i]][p[j]]==2) MRG(p[i],p[j]);
}
}
for(i=1; i<=pi; i++){
V[FND(p[i])].push_back(p[i]);
}
for(i=1; i<=a; i++){
if(V[i].size()==2) return 0;
if(V[i].size()<=1) continue;
for(ii=0; ii<V[i].size(); ii++){
for(jj=ii+1; jj<V[i].size(); jj++){
c=V[i][ii];d=V[i][jj];
if(f[c][d]!=2) return 0;
}
}
for(jj=0; jj<V[i].size(); jj++){
if(jj!=0) c=V[i][jj-1]; else c=V[i][V[i].size()-1];
d=V[i][jj];
bo[c][d]=bo[d][c]=1;
}
}
ANS.resize(a);
for(i=0; i<a; i++) ANS[i].resize(a);
for(i=0; i<a; i++){
for(j=0; j<a; j++){
ANS[i][j]=bo[i+1][j+1];
}
}
build(ANS);
return 1;
}
