#include "supertrees.h"
#include <vector>
#include<bits/stdc++.h>
using namespace std;
bool ck (vector<vector<int>> p, vector<vector<int>> answer) {
int n = p.size();
vector<vector<int>> v(n, vector<int>()), ans(n, vector<int>(n));
vector<bool> f(n);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (answer[i][j]) v[i].emplace_back(j);
}
}
auto dfs = [&] (auto &&dfs, int st, int cur) {
if (f[cur]) return; f[cur] = 1;
ans[st][cur]++;
for (auto &e: v[cur]) {
dfs(dfs, st, e);
}
f[cur] = 0;
};
for (int i = 0; i < n; i++) {
dfs(dfs, i, i);
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (ans[i][j] != p[i][j]) return 0;
}
}
return 1;
}
int construct(std::vector<std::vector<int>> p) {
int n = p.size();
std::vector<std::vector<int>> answer(n, vector<int>(n));
auto add = [&] (int x, int y) {
answer[x][y] = answer[y][x] = 1;
};
vector<int> par(n), par2(n);
iota(par.begin(), par.end(), 0);
iota(par2.begin(), par2.end(), 0);
function<int(int)> fset = [&] (int x) {return (par[x] == x ? x : par[x] = fset(par[x]));};
function<int(int)> fset2 = [&] (int x) {return (par2[x] == x ? x : par2[x] = fset2(par2[x]));};
auto mg = [&] (int x, int y) {
if ((x = fset(x)) == (y = fset(y))) return;
par[y] = x;
};
auto mg2 = [&] (int x, int y) {
if ((x = fset2(x)) == (y = fset2(y))) return;
par2[y] = x;
};
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (p[i][j]) mg(i, j);
}
}
for (int i = 0; i < n; i++) {
if (fset(i) != i) continue;
vector<int> c, cc;
for (int j = 0; j < n; j++) {
if (fset(j) == i) c.emplace_back(j);
}
int csz = c.size();
for (int j = 0; j < csz; j++) {
for (int k = 0; k < csz; k++) {
if (c[j] != c[k] && p[c[j]][c[k]] == 1) mg2(c[j], c[k]);
}
}
for (int j = 0; j < csz; j++) {
if (fset2(c[j]) != c[j]) continue;
cc.emplace_back(c[j]);
vector<int> c2;
for (int k = 0; k < csz; k++) {
if (fset2(c[k]) == c[j]) c2.emplace_back(c[k]);
}
int csz2 = c2.size();
for (int k = 0; k < csz2 - 1; k++) {
add(c2[k], c2[k + 1]);
}
}
sort(cc.begin(), cc.end()); cc.resize(unique(cc.begin(), cc.end()) - cc.begin());
int ccsz = cc.size();
for (int j = 0; j < ccsz; j++) {
add(cc[j], cc[(j + 1) % ccsz]);
}
}
for (int i = 0; i < n; i++) {
answer[i][i] = 0;
}
auto res = ck(p, answer);
if (!res) return 0;
build(answer);
return 1;
}
