#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long;
struct DSU {
vector<int> parent;
void init(int n)
{
parent.resize(n);
for(int i=0;i<n;++i)
parent[i] = i;
}
int find(int x)
{
if(parent[x] != x)
parent[x] = find(parent[x]);
return parent[x];
}
void unite(int a,int b)
{
int u = find(a), v = find(b);
if(u != v)
{
parent[u] = v;
}
}
};
int construct(vector<vector<int>> p) {
int n = p.size();
if(n == 1)
{
build({{0}});
return 1;
}
DSU d;
d.init(n);
for(int i=0;i<n;++i)
{
for(int j=i+1;j<n;++j)
{
if(p[i][j] == 1)
{
d.unite(i,j);
}
}
}
for(int i=0;i<n;++i)
{
for(int j=i+1;j<n;++j)
{
if(p[i][j] == 0 && d.find(i) == d.find(j))
return 0;
else if(p[i][j] == 1 && d.find(i) != d.find(j))
return 0;
}
}
vector<vector<int>> ans(n,vector<int>(n));
for(int i=0;i<n;++i)
{
int root = d.find(i);
for(int j=i+1;j<n;++j)
{
if(root == d.find(j) && p[i][j] == 1)
{
ans[i][j] = 1;
ans[j][i] = 1;
}
}
}
build(ans);
return 1;
}
