#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
struct DSU {
vector<int> p, sz;
DSU(int n = 0) : p(n), sz(n, 1) { iota(p.begin(), p.end(), 0); }
int find(int x) { return p[x] == x ? x : p[x] = find(p[x]); }
void merge(int a, int b) {
a = find(a);
b = find(b);
if (a == b) return;
if (sz[a] < sz[b]) swap(a, b);
p[b] = a;
sz[a] += sz[b];
}
};
int construct(vector<vector<int>> p) {
int n = (int)p.size();
DSU dsu(n);
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
if (p[i][j] == 1) dsu.merge(i, j);
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++) {
bool same = (dsu.find(i) == dsu.find(j));
if ((p[i][j] == 0 && same) || (p[i][j] == 1 && !same)) return 0;
}
vector<vector<int>> b(n, vector<int>(n, 0));
unordered_map<int, vector<int>> buckets;
for (int v = 0; v < n; ++v) buckets[dsu.find(v)].push_back(v);
for (auto& kv : buckets) {
const vector<int>& v = kv.second;
for (size_t k = 1; k < v.size(); ++k) {
int u = v[0], w = v[k];
b[u][w] = b[w][u] = 1;
}
}
build(b);
return 1;
}
