#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
const int N=1005;
int par2[N],par1[N],sz[N];
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]=i;
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);
}
}
}
for(int i=0;i<n;i++)
{
sz[i]=0;
if(get2(i)==i)
{
vector<int> cur;
for(int j=0;j<n;j++)
{
if(i==get2(j))
{
cur.push_back(j);
}
}
sz[i]=cur.size();
for(auto c:cur)
{
for(auto d:cur)
{
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 j=0;j+1<cur.size();j++)
{
ans[cur[j]][cur[j+1]]=1;
ans[cur[j+1]][cur[j]]=1;
}
}
}
for(int i=0;i<n;i++)ans[i][i]=0;
build(ans);
return 1;
}
