#include "supertrees.h"
#include <bits/stdc++.h>
template <class T>
using Vec = std::vector<T>;
struct DSU {
Vec<int> par;
DSU(const int n): par(n, -1) { }
int find(const int u) {
return par[u] < 0 ? u : par[u] = find(par[u]);
}
void merge(int x, int y) {
x = find(x);
y = find(y);
if (x == y) return;
if (par[x] > par[y]) std::swap(x, y);
par[x] += par[y];
par[y] = x;
}
};
int construct(Vec<Vec<int>> p) {
const auto n = (int) p.size();
std::array<Vec<std::pair<int, int>>, 3> pair;
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
if (p[i][j] == 3) {
return 0;
}
pair[p[i][j]].emplace_back(i, j);
}
}
DSU all(n), one(n);
for (int k = 1; k <= 2; ++k) {
for (const auto [x, y]: pair[k]) {
all.merge(x, y);
}
}
for (const auto [x, y]: pair[1]) {
one.merge(x, y);
}
for (const auto [x, y]: pair[0]) {
if (all.find(x) == all.find(y)) {
return 0;
}
}
for (const auto [x, y]: pair[2]) {
if (one.find(x) == one.find(y)) {
return 0;
}
}
Vec<Vec<int>> ret(n, Vec<int>(n));
const auto add_edge = [&](const int x, const int y) {
ret[x][y] = ret[y][x] = 1;
};
for (int i = 0; i < n; ++i) {
const auto j = one.find(i);
if (i != j) {
add_edge(i, j);
}
}
std::map<int, std::set<int>> cycle;
for (const auto [x, y]: pair[2]) {
cycle[all.find(x)].insert(one.find(x));
cycle[all.find(y)].insert(one.find(y));
}
for (const auto [_, s]: cycle) {
Vec<int> v(s.begin(), s.end());
const auto k = (int) v.size();
if (k == 1 || k == 2) {
return 0;
}
for (int i = 0; i < k; ++i) {
add_edge(v[i], v[(i + 1) % k]);
}
}
build(ret);
return 1;
}
