#include "supertrees.h"
#include <bits/stdc++.h>
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define mkp make_pair
#define in insert
#define er erase
#define fd find
#define fr first
#define sc second
#define all(x) x.begin(),x.end()
#define lun(x) (int)x.size()
typedef long long ll;
typedef long double ld;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll llinf=(1LL<<60);
const int inf=(1<<30);
const int nmax=1e3+50;
const ll mod=1e9+7;
using namespace std;
int n,i,j,t,p1[nmax],p2[nmax];
vector<vector<int> >b;
vector<int>v1[nmax],v2[nmax],vc;
int fnd1(int x)
{
if(p1[x]==x)return x;
return p1[x]=fnd1(p1[x]);
}
void uni1(int x,int y)
{
x=fnd1(x),y=fnd1(y);
if(x==y)return;
p1[x]=y;
}
int fnd2(int x)
{
if(p2[x]==x)return x;
return p2[x]=fnd2(p2[x]);
}
void uni2(int x,int y)
{
x=fnd2(x),y=fnd2(y);
if(x==y)return;
p2[x]=y;
}
int construct(vector<vector<int> > r)
{
n=lun(r);
for(i=0;i<n;i++)for(j=0;j<n;j++)if(r[i][j]==3)return 0;
for(i=0;i<n;i++)p1[i]=p2[i]=i;
for(i=0;i<n;i++)for(j=0;j<n;j++)if(r[i][j])uni1(i,j);
for(i=0;i<n;i++)for(j=0;j<n;j++)if(!r[i][j] && fnd1(i)==fnd1(j))return 0;
for(i=0;i<n;i++)for(j=0;j<n;j++)if(r[i][j]==1)uni2(i,j);
for(i=0;i<n;i++)for(j=0;j<n;j++)if(r[i][j]!=1 && fnd2(i)==fnd2(j))return 0;
for(i=0;i<n;i++)v1[fnd1(i)].pb(i);
b.resize(n);
for(i=0;i<n;i++)b[i].resize(n);
for(i=0;i<n;i++)
{
if(v1[i].empty())continue;
for(j=0;j<lun(v1[i]);j++)v2[fnd2(v1[i][j])].pb(v1[i][j]);
vc.clear();
for(j=0;j<n;j++)
{
if(v2[j].empty())continue;
for(t=0;t<lun(v2[j])-1;t++)
{
b[v2[j][t]][v2[j][t+1]]=b[v2[j][t+1]][v2[j][t]]=1;
}
vc.pb(j);
v2[j].clear();
}
if(lun(vc)==2)return 0;
for(j=0;j<lun(vc)-1;j++)b[vc[j]][vc[j+1]]=b[vc[j+1]][vc[j]]=1;
if(lun(vc)!=1)b[vc[0]][vc.back()]=b[vc.back()][vc[0]]=1;
}
build(b);
return 1;
}
/*int main()
{
//freopen("sol.in","r",stdin);
//freopen("sol.out","w",stdout);
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
return 0;
}*/
