#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
#define dbg(x) cerr << #x << ": " << x << endl;
struct DSU {
vector<int> parent;
vector<int> size;
int comps_n;
DSU(int n) {
parent.resize(n);
iota(parent.begin(), parent.end(), 0);
size.assign(n, 1);
comps_n = n;
}
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));
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);
}
}
}
auto add_edge = [&](int u, int v) {
g[u][v] = g[v][u] = 1;
};
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();
if (m == 1) continue;
DSU curr_groups(m);
vector<int> cycle;
bool has_cycle = false;
for (int i = 0; i < m; ++i) {
int u = comp[i];
bool has_one = false;
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;
break;
}
if (p[u][v] >= 2) {
has_cycle = true;
}
if (p[u][v] == 1) {
curr_groups.unite(i, j);
has_one = true;
}
}
if (!has_one) {
cycle.push_back(u);
}
}
if (!has_cycle) {
for (int i = 0; i < m - 1; ++i) {
add_edge(comp[i], comp[i + 1]);
}
continue;
}
map<int, vector<int>> groupsf;
for (int i = 0; i < m; ++i) {
if (curr_groups.size[curr_groups.find(i)] > 1) {
groupsf[curr_groups.find(i)].push_back(comp[i]);
}
}
int groups_n = groupsf.size();
int cycle_size = cycle.size();
for (int i = 0; i < cycle_size - 1; ++i) {
add_edge(cycle[i], cycle[i + 1]);
}
if (groups_n == 0) {
if (cycle_size == 2) {
ok = false;
break;
}
add_edge(cycle[0], cycle.back());
continue;
}
vector<vector<int>> groups(groups_n);
{
int i = 0;
for (const auto& [f, v] : groupsf) {
groups[i] = v;
++i;
}
}
for (int i = 0; i < groups_n; ++i) {
int b = groups[i].size();
for (int j = 0; j < b - 1; ++j) {
add_edge(groups[i][j], groups[i][j + 1]);
}
}
for (int i = 0; i < groups_n - 1; ++i) {
add_edge(groups[i].back(), groups[i + 1].back());
}
if (!cycle.empty()) {
add_edge(groups[0].back(), cycle[0]);
add_edge(groups.back().back(), cycle.back());
} else {
add_edge(groups[0].back(), groups.back().back());
}
}
// for (int i = 0; i < n; ++i) {
// for (int j = 0; j < n; ++j) {
// if (g[i][j] == 1) {
// cout << i << ' ' << j << '\n';
// }
// }
// cout << '\n';
// }
if (ok) {
build(g);
return 1;
}
return 0;
}
// int main() {
// int n;
// cin >> n;
// vector<vector<int>> p(n, vector<int>(n));
// for (int i = 0; i < n; ++i) {
// for (int j = 0; j < n; ++j) {
// cin >> p[i][j];
// }
// }
// construct(p);
// }
