#include "supertrees.h"
#include <vector>
#include <set>
#include <iostream>
using namespace std;
int const N=1010;
int par[N]={};
int comp[N]={};
int ways[N]={};
vector<int>ch[N]={},nei[N]={};
bool stk[N]={};
vector<vector<int>>ans;
int root(int n)
{
return (n==par[n]?n:par[n]=root(par[n]));
}
void merge(int u,int v)
{
u=root(u);
v=root(v);
if (u==v)
return;
par[v]=u;
ch[u].push_back(v);
}
vector<int>z;
void get(int x)
{
z.push_back(x);
for (auto i:ch[x])
get(i);
}
void dfs(int u)
{
ways[u]++;
if (ways[u]>3)
return;
stk[u]=1;
for (auto i:nei[u])
{
if (stk[i]) continue;
dfs(i);
}
stk[u]=0;
}
int construct(vector<vector<int>> p)
{
int n=p.size();
ans=vector<vector<int>>(n,vector<int>(n,0));
for (int i=0;i<n;i++)
par[i]=i;
for (int i=0;i<n;i++)
for (int j=i+1;j<n;j++)
{
if (p[i][j]==1)
{
if (root(i)==root(j)) continue;
ans[root(i)][root(j)]=ans[root(j)][root(i)]=1;
merge(i,j);
}
}
for (int i=0;i<n;i++)
{
set<int>s;
for (int j=0;j<n;j++)
{
if (p[i][j]>1)
s.insert(p[i][j]);
}
if (s.size()>1)
return 0;
}
for (int i=0;i<n;i++)
{
if (par[i]==i)
{
z={};
get(i);
for (auto j:z)
{
if (p[j]!=p[i])
return 0;
}
}
}
for (int i=0;i<n;i++)
{
if (root(i)==i)
{
// cout<<i<<endl;
set<int>s;
int mx=0;
for (int j=0;j<n;j++)
{
mx=max(mx,p[i][j]);
if (p[i][j])
s.insert(root(j));
}
vector<int>g={begin(s),end(s)};
if (mx==1)
continue;
int sz=g.size();
if (mx+1>sz)
return 0;
// for (auto i:g)
// cout<<i<<' ';
// cout<<endl;
for (int j=0;j<sz;j++)
ans[g[j]][g[(j+1)%sz]]=ans[g[(j+1)%sz]][g[j]]=1;
if (mx==3)
ans[g.back()][g[1]]=ans[g[1]][g.back()]=1;
for (auto j:g)
merge(i,j);
}
}
for (int i=0;i<n;i++)
{
for (int j=i+1;j<n;j++)
{
if (ans[i][j])
{
// cout<<i<<' '<<j<<endl;
nei[i].push_back(j);
nei[j].push_back(i);
}
}
}
for (int i=0;i<n;i++)
{
for (int j=0;j<n;j++)
ways[j]=0;
dfs(i);
for (int j=0;j<n;j++)
{
if (ways[j]!=p[i][j])
return 0;
}
}
build(ans);
return 1;
}
