#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
// DSU
int root(int i, vector<int> &parent) {
return parent[i] < 0 ? i : (parent[i] = root(parent[i], parent));
}
bool unite(int i, int j, vector<int> &parent) {
i = root(i, parent), j = root(j, parent);
if (i == j) return false;
if (parent[i] < parent[j]) swap(i, j);
parent[j] += parent[i];
parent[i] = j;
return true;
}
int construct(vector<vector<int>> p) {
int n = p.size();
vector<vector<int>> answer(n, vector<int>(n));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (p[i][j] == 3) return 0;
}
}
vector<int> parent(n, -1);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (p[i][j]) unite(i, j, parent);
}
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (!p[i][j] && root(i, parent) == root(j, parent)) return 0;
}
}
vector<int> parent2(n, -1);
// now within components
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (root(i, parent) != root(j, parent)) continue;
if (p[i][j] == 1) unite(i, j, parent2);
}
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (root(i, parent2) == root(j, parent2) && p[i][j] != 1) return 0;
}
}
auto connect = [&](int i, int j) {answer[i][j] = answer[j][i] = 1;};
vector<vector<vector<int>>> g(n, vector<vector<int>>(n));
for (int i = 0; i < n; ++i) { // chains
int x = root(i, parent), y = root(i, parent2);
if (!g[x][y].empty()) connect(g[x][y].back(), i);
g[x][y].push_back(i);
}
for (int x = 0; x < n; ++x) { // cycle using endpoints of chains
vector<int> ys;
for (int y = 0; y < n; ++y) {
if (!g[x][y].empty()) ys.push_back(y);
}
int m = ys.size();
if (m <= 1) continue;
if (m == 2) return 0;
for (int i = 0; i < m; ++i) connect(g[x][ys[i]][0], g[x][ys[(i+1)%m]][0]);
}
build(answer);
return 1;
}
