#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
struct DSU {
vector<int> p, sz;
DSU(int n) : p(n, -1), sz(n, 1) {}
int find(int v) { return p[v] == -1 ? v : p[v] = find(p[v]); }
void unite(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++) {
if (p[i][i] != 1) return 0;
for (int j = 0; j < n; j++) {
if (p[i][j] != p[j][i]) return 0;
if (i != j && p[i][j] == 1) return 0;
}
}
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
if (p[i][j] > 0) dsu.unite(i, j);
for (int i = 0; i < n; ++i)
for (int j = i + 1; j < n; ++j)
if (dsu.find(i) == dsu.find(j) && p[i][j] != 2) return 0;
unordered_map<int, vector<int>> comp;
for (int v = 0; v < n; ++v) comp[dsu.find(v)].push_back(v);
vector<pair<int, int>> edges;
for (auto& kv : comp) {
const vector<int>& g = kv.second;
int k = (int)g.size();
if (k == 2) return 0;
if (k <= 1) continue;
for (int i = 0; i < k; i++) {
int u = g[i], v = g[(i + 1) % k];
edges.push_back({u, v});
}
}
vector<vector<int>> b(n, vector<int>(n, 0));
for (auto e : edges) {
b[e.first][e.second] = b[e.second][e.first] = 1;
}
build(b);
return 1;
}
