#include <bits/stdc++.h>
#include "supertrees.h"
using namespace std;
#define vi vector<int>
#define vvi vector<vi>
#define loop(a,b,c) for(int a = b; a<(int)c; a++)
struct DSU{
vi leader;
vi siz;
void init(int n){
leader.resize(n+1);
siz.resize(n+1);
for (int i = 0; i<n; i++){
leader[i]=i;
siz[i]=1;
}
}
int Find(int v){
if (leader[v]==v)return v;
leader[v]=Find(leader[v]);
return leader[v];
}
bool same_set(int a, int b){
return Find(a)==Find(b);
}
void Union(int a, int b){
a=Find(a);
b=Find(b);
if (a==b)return;
if (siz[a]<siz[b])swap(a,b);
leader[b]=a;
siz[a]+=siz[b];
}
};
bool vis_branch[1502];
bool vis_comp[1502];
int nr_branch[1502];
int nr_comp[1502];
int construct(vvi p){
int n=p.size();
DSU compound,branch;
compound.init(n);
branch.init(n);
vvi wyn;
wyn.resize(n);
loop(i,0,n)wyn[i].resize(n);
loop(i,0,n){
loop(j,0,n){
if (p[i][j]){
if (p[i][j]==3)return 0;
compound.Union(i,j);
if (p[i][j]==1)branch.Union(i,j);
}
}
}
loop(i,0,n){
loop(j,i+1,n){
if (p[i][j]==0 && compound.same_set(i,j))return 0;
if (p[i][j]==2 && branch.same_set(i,j))return 0;
}
}
vvi single;
vvi cycle;
int iter=0,iter2=0;
loop(i,0,n){
if (!vis_branch[branch.Find(i)]){
if (!vis_comp[compound.Find(i)]){
vis_comp[compound.Find(i)]=true;
cycle.push_back({i});
nr_comp[compound.Find(i)]=iter2++;
}
else cycle[nr_comp[compound.Find(i)]].push_back(i);
vis_branch[branch.Find(i)]=true;
single.push_back({i});
nr_branch[branch.Find(i)]=iter++;
}
else single[nr_branch[branch.Find(i)]].push_back(i);
}
loop(i,0,iter){
loop(j,1,single[i].size()){
wyn[single[i][0]][single[i][j]]=wyn[single[i][j]][single[i][0]]=1;
}
}
loop(i,0,iter2){
if (cycle[i].size()==1)continue;
else if (cycle[i].size()==2)return 0;
wyn[cycle[i][0]][cycle[i].back()]=wyn[cycle[i].back()][cycle[i][0]]=1;
loop(j,1,cycle[i].size()){
wyn[cycle[i][j-1]][cycle[i][j]]=wyn[cycle[i][j]][cycle[i][j-1]]=1;
}
}
build(wyn);
return 1;
}
