#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];
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]!=0)
{
//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]==0)
{
//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++)
{
if(v[i].size()<=1)continue;
if(v[i].size()==2)return 0;
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;
}
if(p[v[i][0]][v[i][1]]==2)
ans[v[i][0]][v[i][v[i].size()-1]]=ans[v[i][v[i].size()-1]][v[i][0]]=1;
}
build(ans);
return 1;
}
