#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int,int> pi;
typedef vector<pi> pii;
typedef tuple<int,int,int> ti;
typedef vector<ll> li;
typedef vector<li> lii;
#define REP(i,a,b) for(int i=a;i<b;i++)
#define F first
#define S second
#define PB push_back
#define LSOne(s) ((s)&(-s))
#define all(x) x.begin(),x.end()
ll INF=1000000000000000010;
int inf=1e9+10;
ll M=1e9+7;
int n;
vi p,s;
vii a;
int parent(int x){
if(p[x]==x)return x;
return p[x]=parent(p[x]);
}
void merge(int x,int y){
x=parent(x);
y=parent(y);
if(x==y)return;
if(s[x]<s[y])swap(x,y);
s[x]+=s[y];
p[y]=x;
}
int construct(std::vector<std::vector<int>> R) {
n=R.size();
REP(i,0,n)REP(j,0,n)if(R[i][j]==3)return 0;
vii ans(n,vi(n,0));
p.resize(n);s.resize(n,1);
REP(i,0,n)p[i]=i;
REP(i,0,n)REP(j,0,n)if(i!=j&&R[i][j]==1&&parent(i)!=parent(j)){
merge(i,j);
ans[i][j]=1;
ans[j][i]=1;
}
REP(i,0,n)if(R[parent(i)]!=R[i])return 0;
REP(i,0,n)REP(j,0,n)if(parent(i)==parent(j)&&R[i][j]==0)return 0;
a.resize(n);
REP(i,0,n)a[parent(i)].PB(i);
REP(i,0,n)sort(all(a[i]));
vi vis(n,0),cnt(n,0);
REP(i,0,n)REP(j,0,n)if(R[i][j]==2)cnt[i]++;
REP(i,0,n)if(cnt[i]==1)return 0;
REP(i,0,n)if(!vis[i]&&a[i].size()){
if(cnt[i]==0)continue;
set<int> st,st2;
int x=parent(a[i][0]);
st.insert(x);
REP(j,0,n)if(R[x][j]==2)st.insert(parent(j));
for(auto u:st){
if(vis[u])return 0;
vis[u]=1;
for(auto v:a[u])st2.insert(v);
}
int sz=st2.size();
vi arr;
for(auto u:st){
if(cnt[u]!=sz-a[u].size())return 0;
REP(j,0,n)if(R[u][j]==2&&st2.count(j)==0)return 0;
arr.PB(u);
}
int y=arr.size();
REP(i,0,y){
ans[arr[i]][arr[(i+1)%y]]=1;
ans[arr[(i+1)%y]][arr[i]]=1;
}
}
build(ans);
return 1;
}
