#include "supertrees.h"
#include <vector>
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
vector<int>g[1005], v[1005], v2[1005];
int sz[1005], par[1005];
int parent(int v)
{
while(v!=par[v]) v=par[v];
return v;
}
bool merge(int u, int v)
{
u=parent(u);
v=parent(v);
if(u==v) return 0;
if(sz[u]<sz[v])
sz[v]+=sz[u], par[u]=v;
else sz[u]+=sz[v], par[v]=u;
return 1;
}
int construct(vector<vector<int>> p)
{
int n = p.size();
for(int i=0; i<=n; i++)
sz[i]=1, par[i]=i;
for(int i=0; i<n; i++)
{
for(int j=i+1; j<n; j++)
{
if(p[i][j]==1)
v[i].pb(j), v[j].pb(i);
if(p[i][j])
v2[i].pb(j);
}
}
for(int i=0; i<n; i++)
{
if(v[i].size() and merge(v[i][0], i))
{
// cout<<i<<' '<<v[i][0]<<endl;
g[i].pb(v[i][0]);
g[v[i][0]].pb(i);
for(int j=1; j<(int)v[i].size(); j++)
{
// cout<<v[i][j]<<' '<<v[i][j-1]<<endl;
g[v[i][j]].pb(v[i][j-1]);
g[v[i][j-1]].pb(v[i][j]);
merge(v[i][j], v[i][j-1]);
}
}
}
/*for(int i=0; i<n; i++)
{
for(int u : g[i])
cout<<i<<' '<<u<<endl;
}
*/
for(int i=0; i<n; i++)
{
int lst=-1;
//cout<<i<<' '<<v2[i].size()<<' '<<i<<' '<<(v2[i].size()? v2[i][0] : -1)<<endl;
if(v2[i].size() and merge(v2[i][0], i))
{
//cout<<i<<endl;
g[i].pb(v2[i][0]);
g[v2[i][0]].pb(i);
lst=v2[i][0];
for(int j=1; j<(int)v2[i].size(); j++)
{
if(merge(v2[i][j], v2[i][j-1]))
{
g[v2[i][j]].pb(v2[i][j-1]);
g[v2[i][j-1]].pb(v2[i][j]);
lst=v2[i][j];
}
}
g[i].pb(lst);
g[lst].pb(i);
}
}
vector<vector<int>>ans(n, vector<int>(n, 0));
for(int i=0; i<n; i++)
{
for(int u : g[i])
ans[i][u]=1, ans[u][i]=1;
}
build(ans);
return 1;
}
