#include <bits/stdc++.h>
#include "supertrees.h"
using namespace std;
void dfs(int node, const vector<vector<int>> &p, int c, vector<int> &comp) {
comp[node] = c;
int n = p.size();
for (int i = 0; i < n; i++) {
if (p[node][i] > 0 && comp[i] == -1) {
dfs(i, p, c, comp);
}
}
}
int construct(vector<vector<int>> p) {
int n = p.size();
vector<vector<int>> b(n, vector<int>(n, 0));
vector<int> comp(n, -1);
int num_components = 0;
for (int i = 0; i < n; i++) {
if (comp[i] == -1) {
dfs(i, p, num_components++, comp);
}
}
for (int id = 0; id < num_components; id++) {
vector<int> group;
for (int i = 0; i < n; i++) {
if (comp[i] == id) group.push_back(i);
}
bool has1 = false, has2 = false;
for (int i : group) {
for (int j : group) {
if (i == j) continue;
if (p[i][j] == 1) has1 = true;
if (p[i][j] == 2) has2 = true;
}
}
if (has1 && has2) return 0;
int m = group.size();
if (has1) {
for (int i = 0; i + 1 < m; i++) {
int u = group[i], v = group[i + 1];
b[u][v] = b[v][u] = 1;
}
} else if (has2) {
if (m < 3) return 0;
for (int i = 0; i < m; i++) {
int u = group[i], v = group[(i + 1) % m];
b[u][v] = b[v][u] = 1;
}
}
}
build(b);
return 1;
}
