#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
long long n,dsu[2][1069];
vector<long long> vl[1069];
long long fd(long long xx,long long x)
{
if(dsu[xx][x]!=x)
{
dsu[xx][x]=fd(xx,dsu[xx][x]);
}
return dsu[xx][x];
}
int construct(vector<vector<int>> a)
{
long long i,j,ii,k,l,sz;
vector<int> v;
vector<vector<int>> sq;
n=a.size();
for(i=0;i<n;i++)
{
for(ii=0;ii<2;ii++)
{
dsu[ii][i]=i;
}
sq.push_back(v);
for(j=0;j<n;j++)
{
sq[i].push_back(0);
}
}
for(i=0;i<n;i++)
{
for(j=i+1;j<n;j++)
{
if(a[i][j]==1&&fd(0,i)!=fd(0,j))
{
sq[i][j]=1;
sq[j][i]=1;
for(ii=0;ii<2;ii++)
{
dsu[ii][fd(ii,j)]=fd(ii,i);
}
}
}
}
for(i=0;i<n;i++)
{
for(j=i+1;j<n;j++)
{
if(a[i][j]==2)
{
dsu[1][fd(1,j)]=fd(1,i);
}
}
}
for(i=0;i<n;i++)
{
if(fd(0,i)==i)
{
vl[fd(1,i)].push_back(i);
}
}
for(i=0;i<n;i++)
{
sz=vl[i].size();
if(sz==2)
{
return 0;
}
for(j=0;j<sz;j++)
{
k=vl[i][j];
if(j)
{
sq[k][l]=1;
sq[l][k]=1;
}
l=k;
}
if(sz>=3)
{
sq[l][vl[i][0]]=1;
sq[vl[i][0]][l]=1;
}
}
for(i=0;i<n;i++)
{
for(j=i+1;j<n;j++)
{
if((!a[i][j]&&fd(1,i)==fd(1,j))||(a[i][j]==2&&fd(0,i)==fd(0,j))||a[i][j]==3)
{
return 0;
}
}
}
build(sq);
return 1;
}
