#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
#define arr array
#define vec vector
const int N = 1e3 + 5;
int n;
arr<arr<int, N>, N> p;
arr<vec<int>, N> ln;
arr<int, N> ln_src;
void ln_dfs(int u, int src) {
ln_src[u] = src, ln[src].push_back(u);
for (int v = 1; v <= n; v++) {
if (p[u][v] != 1) continue;
if (ln_src[v]) continue;
ln_dfs(v, src);
}
}
void ln_cmp() {
for (int u = 1; u <= n; u++) {
if (ln_src[u]) continue;
ln_dfs(u, u);
}
// for (int u = 1; u <= n; u++) {
// for (int v : ln[u]) cout << v << " ";
// cout << '\n';
// }
}
arr<vec<int>, N> cnn;
arr<int, N> cnn_src;
void cnn_dfs(int u, int src) {
cnn_src[u] = src, cnn[src].push_back(u);
for (int v = 1; v <= n; v++) {
if (!p[u][v]) continue;
if (cnn_src[v]) continue;
cnn_dfs(v, src);
}
}
void cnn_cmp() {
for (int u = 1; u <= n; u++) {
if (cnn_src[u]) continue;
cnn_dfs(u, u);
}
// for (int u = 1; u <= n; u++) {
// for (int v : cnn[u]) cout << v << " ";
// cout << '\n';
// }
}
arr<arr<int, N>, N> ans;
void upd(int u, int v) { ans[u][v] = ans[v][u] = 1; }
void ans_cmp() {
for (int c = 1; c <= n; c++) {
set<int> unq;
for (int u : cnn[c]) unq.insert(ln_src[u]);
for (auto it = unq.begin(); it != unq.end(); it++) {
for (int i = 0; i < ln[*it].size() - 1; i++)
upd(ln[*it][i], ln[*it][i + 1]);
if (unq.size() == 1) continue;
auto nx = (next(it, 1) == unq.end()) ? unq.begin() : next(it, 1);
upd(*it, *nx);
}
}
}
bool chck() {
for (int u = 1; u <= n; u++) {
for (int v = 1; v <= n; v++) {
if (cnn_src[u] != cnn_src[v]) {
if (p[u][v] != 0) return false;
} else if (ln_src[u] != ln_src[v]) {
if (p[u][v] != 2) return false;
} else {
if (p[u][v] != 1) return false;
}
}
}
return true;
}
int construct(vec<vec<int>> _p) {
n = _p.size();
for (int u = 1; u <= n; u++)
for (int v = 1; v <= n; v++)
p[u][v] = _p[u - 1][v - 1];
ln_cmp();
cnn_cmp();
ans_cmp();
if (!chck()) return 0;
vec<vec<int>> ans_lst(n);
for (int u = 1; u <= n; u++)
for (int v = 1; v <= n; v++)
ans_lst[u - 1].push_back(ans[u][v]);
build(ans_lst);
return 1;
}
