#include <bits/stdc++.h>
#include "supertrees.h"
using namespace std;
int find_par(int node, vector<int> &par) {
if (node == par[node]) return node;
return par[node] = find_par(par[node], par);
}
void unite(int a, int b, vector<int> &par, vector<vector<int>> &adj, vector<vector<int>> &groups) {
a = find_par(a, par);
b = find_par(b, par);
if (a != b) {
par[b] = a;
adj[a][b] = adj[b][a] = 1;
for (int x : groups[b]) groups[a].push_back(x);
groups[b].clear();
}
}
int construct(vector<vector<int>> p) {
int n = p.size();
vector<vector<int>> adj(n, vector<int>(n, 0));
vector<int> par(n);
iota(par.begin(), par.end(), 0);
vector<vector<int>> groups(n);
for (int i = 0; i < n; i++) groups[i].push_back(i);
for (int i = 0; i < n; i++) {
for (int j = i+1; j < n; j++) {
if (p[i][j] == 1) {
int a = find_par(i, par), b = find_par(j, par);
if (a == b) continue;
bool ok = true;
for (int x : groups[a]) {
for (int y : groups[b]) {
if (p[x][y] != 1) ok = false;
}
}
if (!ok) return 0;
unite(i, j, par, adj, groups);
}
if (p[i][j] == 3) return 0;
}
}
vector<int> used(n, false);
for (int i = 0; i < n; i++) {
if (find_par(i, par) != i || used[i]) continue;
vector<int> group;
queue<int> q;
q.push(i);
used[i] = true;
while (!q.empty()) {
int cur = q.front(); q.pop();
group.push_back(cur);
for (int j = 0; j < n; j++) {
if (find_par(j, par) == j && !used[j] && p[cur][j] == 2) {
q.push(j);
used[j] = true;
}
}
}
if (group.size() == 1) continue;
if (group.size() == 2) return 0;
for (int x = 0; x < group.size(); x++) {
for (int y = x + 1; y < group.size(); y++) {
for (int u : groups[group[x]]) {
for (int v : groups[group[y]]) {
if (p[u][v] != 2) return 0;
}
}
}
}
int m = group.size();
for (int j = 0; j < m; j++) {
int u = group[j], v = group[(j + 1) % m];
adj[u][v] = adj[v][u] = 1;
}
}
build(adj);
return 1;
}
