#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
struct dsu {
int n;
vector<int> parent, rank;
dsu(int _n) {
n = _n;
parent.resize(n);
rank.resize(n);
for (int i = 0; i < n; i++) {
parent[i] = i;
rank[i] = 1;
}
}
int get(int x) {
if (parent[x] == x) return x;
return parent[x] = get(parent[x]);
}
bool unite(int x, int y) {
x = get(x), y = get(y);
if (x == y) return false;
if (rank[x] < rank[y]) swap(x, y);
parent[y] = x;
rank[x] += rank[y];
return true;
}
vector<int> all_roots() {
set<int> s;
for (int i = 0; i < n; i++) s.insert(parent[i]);
vector<int> res;
for (auto &x : s) res.push_back(x);
return res;
}
};
void path(vector<vector<int>> &answer, vector<int> nodes) {
if (nodes.size() == 1) return;
for (int i = 1; i < (int)nodes.size(); i++) {
answer[nodes[i - 1]][nodes[i]] = 1;
answer[nodes[i]][nodes[i - 1]] = 1;
}
}
void cycle(vector<vector<int>> &answer, vector<int> nodes) {
if (nodes.size() == 1) return;
path(answer, nodes);
answer[nodes.back()][nodes[0]] = 1;
answer[nodes[0]][nodes.back()] = 1;
}
int construct(vector<std::vector<int>> p) {
int n = p.size();
vector<vector<int>> answer;
answer.resize(n);
for (int i = 0; i < n; i++) {
answer[i].resize(n);
for (int j = 0; j < n; j++) {
answer[i][j] = 0;
}
}
dsu d(n);
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (p[i][j] != p[j][i]) return 0;
if (p[i][j] > 0) d.unite(i, j);
}
}
vector<int> roots = d.all_roots();
int roots_num = (int)roots.size();
unordered_map<int, int> ind;
for (int i = 0; i < roots_num; i++) {
ind[roots[i]] = i;
}
vector<vector<int>> parts(roots_num);
for (int i = 0; i < n; i++) {
parts[ind[d.get(i)]].push_back(i);
}
for (int i = 0; i < roots_num; i++) {
vector<int> &cur = parts[i];
int small_sz = (int)cur.size();
for (int j = 0; j < small_sz; j++) {
for (int k = 0; k < small_sz; k++) {
if (p[cur[j]][cur[k]] == 0) return 0;
}
}
path(answer, cur);
}
build(answer);
return 1;
}
