#include "supertrees.h"
#include <iostream>
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
int inf = 1e9 + 7;
struct dsu {
vector<int> par;
vector<int> sz;
void init(int n) {
par.assign(n, 0);
sz.assign(n, 1);
for (int i = 0; i < n; i++) {
par[i] = i;
}
}
int get_par(int v) {
if (par[v] == v) {
return v;
}
int ans = get_par(par[v]);
par[v] = ans;
return ans;
}
void unitik(int v, int u) {
v = get_par(v);
u = get_par(u);
if (sz[v] < sz[u]) {
swap(v, u);
}
sz[v] += sz[u];
par[u] = v;
}
};
int construct(vector<vector<int>> p) {
int n = p.size();
dsu dsu;
dsu.init(n);
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (p[i][j] > 0 && dsu.get_par(i) != dsu.get_par(j)) {
dsu.unitik(i, j);
}
}
}
bool ok = 1;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (p[i][j] == 0 && dsu.get_par(i) == dsu.get_par(j)) {
ok = 0;
}
}
}
if (!ok) {
return 0;
}
vector<vector<int>> b(n, vector<int>(n));
vector<vector<int>> gr(n);
for (int i = 0; i < n; i++) {
gr[dsu.get_par(i)].push_back(i);
}
for (auto g : gr) {
for (int i = 0; i < g.size() - 1; i++) {
b[g[i]][g[i + 1]] = 1;
b[g[i + 1]][g[i]] = 1;
}
}
build(b);
return 1;
}
