#include "supertrees.h"
#include "bits/stdc++.h"
using namespace std;
#define pb push_back
const int N = 1005;
int par[N];
int siz[N];
int find(int a)
{
if(par[a]==a) return a;
return par[a]=find(par[a]);
}
void unite(int a,int b)
{
a=find(a),b=find(b);
if(a==b) return;
if(siz[a]>siz[b]) swap(a,b);
siz[b]+=siz[a];
par[a]=b;
}
int construct(vector<vector<int>> p) {
iota(par,par+N,0LL);
fill(siz,siz+N,1LL);
int n = p[0].size();
vector<vector<int>> g(n,vector<int>(n,0));
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
if(p[i][j]) unite(i,j);
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
if(!p[i][j] && find(i)==find(j))
return 0;
vector<int> no[n];
for(int i=0;i<n;i++) no[find(i)].pb(i);
for(int xd=0;xd<n;xd++)
{
if(no[xd].size()<=1) continue;
int m = no[xd].size();
vector<vector<int>> v[m];
set<int> s;
vector<int> deg(m,0);
for(int i=0;i<m;i++)
{
for(int j=i+1;j<m;j++)
{
if(i==j) continue;
if(p[i][j]==2)
{
s.insert(i);
s.insert(j);
deg[i]++;
deg[j]++;
}
}
}
int k=s.size();
if(k==2) return 0;
for(int x:s) if(deg[x]!=k-1) return 0;
if(k>0)
{
int a=*s.begin();
int b=*s.rbegin();
g[a][b]=g[b][a]=1;
}
for(int i=1;i<m;i++)
g[no[xd][i]][no[xd][i-1]]=g[no[xd][i-1]][no[xd][i]]=1;
}
build(g);
return 1;
}
