#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
int a[1024][1024];
int l[1024],s[1024];
int fl(int i)
{
if(i==l[i])return i;
return l[i]=fl(l[i]);
}
void unite(int i,int j)
{
int li=fl(i);
int lj=fl(j);
if(li!=lj)
{
l[li]=lj;
s[lj]+=s[li];
}
}
vector<int> v[200001],v2[200001];
vector<vector<int> > ans;
int construct(std::vector<std::vector<int>> p)
{
int n=p.size();
for(int i=0; i<n; i++)
{
l[i]=i;
s[i]=1;
}
for(int i=0; i<n; i++)
{
ans.push_back({});
for(int j=0; j<n; j++)
{
ans[i].push_back(0);
a[i][j]=p[i][j];
if(a[i][j]==1)
{
//cout<<"+ "<<i<<" "<<j<<endl;
unite(i,j);
}
}
}
for(int i=0; i<n; i++)
{
for(int j=0; j<n; j++)
{
if(a[i][j]!=1)
{
//cout<<i<<" "<<j<<endl;
int li=fl(i);
int lj=fl(j);
if(li==lj)return 0;
}
}
}
for(int i=0; i<n; i++)
{
int li=fl(i);
v[li].push_back(i);
}
for(int i=0; i<n; i++)
l[i]=i,s[i]=1;
for(int i=0; i<n; i++)
{
for(int j=0; j<n; j++)
{
if(v[i].size()==0||v[j].size()==0)continue;
if(a[i][j]==2)
{
//cout<<i<<" + "<<j<<endl;
unite(i,j);
}
}
}
for(int i=0; i<n; i++)
{
if(v[i].size()==0)continue;
int li=fl(i);
v2[li].push_back(i);
}
for(int i=0; i<n; i++)
{
if(v[i].size()<=1)continue;
for(int j=0; j<v[i].size()-1; j++)
{
ans[v[i][j]][v[i][j+1]]=ans[v[i][j+1]][v[i][j]]=1;
}
}
for(int i=0;i<n;i++)
{
//cout<<i<<" : "<<v2[i].size()<<endl;
if(v2[i].size()==2)return 0;
for(int j=0; j<(int)v2[i].size()-1; j++)
{
//cout<<"in"<<endl;
//cout<<v2[i][j]<<" "<<v2[i].size()<<endl;
ans[v2[i][j]][v2[i][j+1]]=ans[v2[i][j+1]][v2[i][j]]=1;
}
if(v2[i].size()>2)ans[v2[i][0]][v2[i][v2[i].size()-1]]=ans[v2[i][v2[i].size()-1]][v2[i][0]]=1;
}
build(ans);
return 1;
}
