#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
struct DSU {
vector<int> parent;
vector<int> size;
DSU(int n) {
parent.resize(n);
iota(parent.begin(), parent.end(), 0);
size.assign(n, 1);
}
int find(int v) {
if (parent[v] == v) {
return v;
} else {
return parent[v] = find(parent[v]);
}
}
void unite(int u, int v) {
if (u == v) return;
u = find(u);
v = find(v);
if (size[u] > size[v]) swap(u, v);
parent[u] = v;
size[v] += size[u];
}
};
int construct(vector<vector<int>> p) {
int n = p.size();
vector<vector<int>> g(n, vector<int>(n));
// 1) must be transitive:
// p[u][w] * p[w][v] = p[v][w] * p[w][u] = p[u][v] = p[v][u], for any u, v, w
bool ok = true;
DSU dsu(n);
for (int u = 0; u < n; ++u) {
for (int v = u + 1; v < n; ++v) {
if (p[u][v] > 0) {
dsu.unite(u, v);
}
}
}
map<int, vector<int>> comps;
for (int v = 0; v < n; ++v) {
comps[dsu.find(v)].push_back(v);
}
for (const auto& [c, comp] : comps) {
int m = comp.size();
map<int, int> color;
for (int i = 0; i < m; ++i) {
int u = comp[i];
for (int j = 0; j < m; ++j) {
if (i == j) continue;
int v = comp[j];
if (u == v) continue;
if (p[u][v] == 0) {
ok = false;
}
if (p[u][v] == 1) {
color[u] = 1;
color[v] = 1;
}
if (p[u][v] == 2) {
if (color[u] != 1) {
color[u] = 2;
}
if (color[v] != 1) {
color[v] = 2;
}
}
}
}
vector<int> line;
int cnt1 = 0;
for (const auto& [v, col] : color) {
if (col == 1) {
++cnt1;
line.push_back(v);
}
}
int cnt2 = 0;
for (const auto& [v, col] : color) {
if (col == 2) {
++cnt2;
line.push_back(v);
}
}
if (cnt2 == 1) {
ok = false;
}
for (int i = 0; i < m - 1; ++i) {
g[line[i]][line[i + 1]] = 1;
g[line[i + 1]][line[i]] = 1;
}
if (cnt1 + cnt2 != m) {
ok = false;
}
if (cnt2 == 0) continue;
g[line[cnt1 - 1]][line.back()] = g[line.back()][line[cnt1 - 1]] = 1;
}
if (ok) {
build(g);
return 1;
}
return 0;
}
