#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
const int N=1e4+10;
int fau[N],fau2[N];
bool vis[N];
vi kt[N];
int Find(int a){
if(fau[a]==a) return a;
return fau[a]=Find(fau[a]);
}
void Union(int a,int b){
a=Find(a),b=Find(b);
fau[a]=b;
}
int Find2(int a){
if(fau2[a]==a) return a;
return fau2[a]=Find2(fau2[a]);
}
void Union2(int a,int b){
a=Find2(a),b=Find2(b);
fau2[a]=fau2[b];
}
int construct(vector<vi> g) {
int n=g.size();
iota(fau,fau+1+n,0);
iota(fau2,fau2+1+n,0);
vector<vi> ans=g;
for(int i=0;i<n;i++){
for(int i2=0;i2<n;i2++) ans[i][i2]=0;
}
for(int i=0;i<n;i++){
for(int i2=0;i2<n;i2++){
if(g[i][i2]==1) Union(i+1,i2+1);
}
}
for(int i=0;i<n;i++){
for(int i2=0;i2<n;i2++){
if(g[i][i2]==2) Union2(Find(i+1),Find(i2+1));
}
}
for(int i=1;i<=n;i++){
int u=Find(i);
if(vis[u]) continue;
vis[u]=1;
kt[Find2(u)].push_back(u);
}
for(int i=1;i<=n;i++){
if(kt[i].size()==2){
return 0;
}
if(kt[i].size()<2) continue;
for(int i2=0;i2<(int)kt[i].size();i2++){
int nxt=kt[i][(i2+1)%kt[i].size()],u=kt[i][i2];
ans[u-1][nxt-1]=1,ans[nxt-1][u-1]=1;
}
}
for(int i=1;i<=n;i++){
int u=Find(i);
if(u!=i) ans[u-1][i-1]=1,ans[i-1][u-1]=1;
}
for(int i=0;i<n;i++){
for(int i2=0;i2<n;i2++){
int u=Find(i+1),u2=Find(i2+1);
int v1=Find2(u),v2=Find2(u2);
if(g[i][i2]==0){
if(u==u2 or v1==v2) return 0;
}
if(g[i][i2]==1){
if(u!=u2) return 0;
}
if(g[i][i2]==2){
if(u==u2 or v1!=v2) return 0;
}
if(g[i][i2]==3) return 0;
}
}
build(ans);
return 1;
}
