#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
struct DSU {
vector<int> rank, parent;
DSU(int n) {
rank.assign(n, 1);
parent.resize(n);
for (int i=0; i<n; i++) {
parent[i] = i;
}
}
int find(int n) {
return (n == parent[n] ? n : parent[n] = find(parent[n]));
}
void unite(int n1, int n2) {
int p1 = find(n1);
int p2 = find(n2);
rank[p1] += rank[p2];
parent[p2] = p1;
}
};
int construct(std::vector<std::vector<int>> p) {
int n = p.size();
vector<vector<int>> ans(n, vector<int>(n, 0));
bool can = true;
for (int i=0; i<n; i++) {
for (int j=0; j<n; j++) {
if (p[i][j] != p[j][i]) can = false;
}
}
if (!can) {
return 0;
}
DSU dsu(n);
for (int i=0; i<n; i++) {
for (int j=0; j<n; j++) {
if (p[i][j] == 1) dsu.unite(i, j);
}
}
for (int i=0; i<n; i++) {
int pi = dsu.find(i);
if (pi==i) {
vector<int> cmp = {i};
for (int j=0; j<n; j++) {
if (j==i) continue;
int pj = dsu.find(j);
if (pj == i) {
cmp.push_back(j);
}
}
for (auto x : cmp) {
ans[i][x] = ans[x][i] = 1;
}
for (auto j1 : cmp) {
for (auto j2 : cmp) {
if (p[j1][j2] == p[j2][j1] && p[j1][j2] == 0) {
return 0;
}
}
}
}
}
for (int i=0; i<n; i++) {
ans[i][i] = 0;
}
build(ans);
return 1;
}
