#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
const int N=1e3;
int reach[N][N],tree_case[N][N];
int par[N];
void init(int n)
{
for(int i=0;i<n;i++)
par[i]=i;
}
int get(int x)
{
if(par[x]==x)return x;
return par[x]=get(par[x]);
}
bool merge(int x,int y)
{
x=get(x);
y=get(y);
if(x==y)return 0;
par[y]=x;
return 1;
}
vector<int> ma[N];
int head;
void dfs(int x)
{
reach[head][x]=1;
for(auto y:ma[x])
if(!reach[head][y])
dfs(y);
}
int construct(std::vector<std::vector<int>> p) {
int n = p.size();
init(n);
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
tree_case[i][j]=reach[i][j]=0;
for(int i=0;i<n;i++)
{
for(int j=i+1;j<n;j++)
{
if(p[i][j]==1)
{
tree_case[i][j]=tree_case[j][i]=merge(i,j);
ma[i].push_back(j);
ma[j].push_back(i);
}
}
}
vector<vector<int>> answer(n,vector<int>(n,0));
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
answer[i][j]=tree_case[i][j];
reach[i][j]=0;
}
head=i;
dfs(i);
for(int j=0;j<n;j++)
{
if(reach[i][j]!=p[i][j])
{
return 0;
}
}
}
build(answer);
return 1;
}
