#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
const int N=1005;
int par2[N],par1[N],sz[N],par3[N];
vector<int> cot[N];
int get3(int x)
{
return (par3[x]==x)?x:par3[x]=get3(par3[x]);
}
void merge3(int x,int y)
{
x=get3(x),y=get3(y);
if(x==y)return;
par3[x]=y;
}
int get1(int x)
{
return (par1[x]==x)?x:par1[x]=get1(par1[x]);
}
void merge1(int x,int y)
{
x=get1(x),y=get1(y);
if(x==y)return;
par1[x]=y;
}
int get2(int x)
{
return (par2[x]==x)?x:par2[x]=get2(par2[x]);
}
void merge2(int x,int y)
{
x=get2(x),y=get2(y);
if(x==y)return;
par2[x]=y;
}
int construct(std::vector<std::vector<int>> p) {
int n = p.size();
auto ans=p;
for(int i=0;i<n;i++)par1[i]=par2[i]=par3[i]=i,cot[i].clear(),sz[i]=0;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
ans[i][j]=0;
if(p[i][j]==3)
{
return 0;
}
if(p[i][j]==2)
{
merge2(i,j);
}
if(p[i][j]>0)
{
merge1(i,j);
}
if(p[i][j]==1)
{
merge3(i,j);
}
}
}
for(int i=0;i<n;i++)
{
if(get3(i)==i)
{
vector<int> cur;
for(int j=0;j<n;j++)
{
if(i==get3(j))
{
cur.push_back(j);
}
}
cot[i]=cur;
for(auto c:cur)
{
for(auto d:cur)
{
if(c==d)continue;
if(p[c][d]<1)
{
return 0;
}
}
}
for(int j=0;j+1<cur.size();j++)
{
ans[cur[j]][cur[j+1]]=1;
ans[cur[j+1]][cur[j]]=1;
}
// now in the cycle we will need to add only a single node for such chains
}
}
for(int i=0;i<n;i++)
{
sz[i]=0;
if(get2(i)==i)
{
set<int> dip;
for(int j=0;j<n;j++)
{
if(i==get2(j))
{
dip.insert(get3(j));
}
}
vector<int> cur(begin(dip),end(dip));
sz[i]=cur.size();
for(auto cp:cur)
{
for(auto dp:cur)
{
// same component have ways equal to one
if(cp==dp)continue;
for(auto c:cot[cp])
{
for(auto d:cot[dp])
{
if(c==d)continue;
if(p[c][d]<2)
{
return 0;
}
}
}
}
}
if(cur.size()==2)
{
// requires multiedges but we cant add multi
return 0;
}
for(int j=0;j+1<cur.size();j++)
{
ans[cur[j]][cur[j+1]]=1;
ans[cur[j+1]][cur[j]]=1;
}
ans[cur.back()][cur[0]]=1;
ans[cur[0]][cur.back()]=1;
}
}
for(int i=0;i<n;i++)
{
if(get1(i)==i)
{
vector<int> cur;
for(int j=0;j<n;j++)
{
if(i==get1(j))
{
cur.push_back(j);
}
}
for(auto c:cur)
{
for(auto d:cur)
{
if(c==d)continue;
if(p[c][d]<1)
{
return 0;
}
}
}
}
}
for(int i=0;i<n;i++)ans[i][i]=0;
build(ans);
return 1;
}
