#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
int construct(vvi p) {
int n = p.size();
vvi ans(n, vi(n));
vvi comp(n);
vi seen(n);
for (int c = 0; c < n; c++) {
auto dfs = [&](auto dfs, int u) -> void {
if (seen[u]) return;
seen[u] = 1;
comp[c].push_back(u);
for (int v = 0; v < n; v++) if (p[u][v]) dfs(dfs, v);
};
dfs(dfs, c);
}
for (int c = 0; c < n; c++) if (comp[c].size()) {
vvi all(4);
vi mixed;
for (int u : comp[c]) {
vi cnt(4);
for (int v : comp[c]) if (u != v) {
cnt[p[u][v]]++;
}
if (cnt[0]) return 0;
if (cnt[2] && cnt[3]) return 0;
if ((cnt[2] || cnt[3]) && cnt[1]) mixed.push_back(u);
else {
if (cnt[1]) all[1].push_back(u);
if (cnt[2]) all[2].push_back(u);
if (cnt[3]) all[3].push_back(u);
}
}
if (all[2].empty() && all[3].empty()) {
int prev = -1;
for (int u : comp[c]) {
if (prev >= 0) ans[u][prev] = ans[prev][u] = 1;
prev = u;
}
}
else if (all[3].empty()) {
if (all[1].size()) return 0;
vi twos;
for (int u : all[2]) {
if (twos.size()) ans[u][twos.back()] = ans[twos.back()][u] = 1;
twos.push_back(u);
}
if (mixed.empty()) {
if (twos.size() < 3) return 0;
ans[twos[0]][twos.back()] = ans[twos.back()][twos[0]] = 1;
}
else {
if (twos.size() < 2) return 0;
int prev = -1;
for (int u : mixed) {
if (prev >= 0) ans[u][prev] = ans[prev][u] = 1;
prev = u;
}
ans[twos[0]][prev] = ans[prev][twos[0]] = 1;
ans[twos.back()][prev] = ans[prev][twos.back()] = 1;
}
}
else if (all[2].empty()) {
return 0;
if (all[1].size()) return 0;
int prev = -1;
for (int u : mixed) {
if (prev >= 0) ans[u][prev] = ans[prev][u] = 1;
prev = u;
}
vi threes;
for (int u : all[3]) {
if (threes.size()) ans[u][threes.back()] = ans[threes.back()][u] = 1;
threes.push_back(u);
}
if (threes.size() < 3) return 0;
ans[threes[0]][prev] = ans[prev][threes[0]] = 1;
ans[threes.back()][prev] = ans[prev][threes.back()] = 1;
}
else return 0;
}
build(ans);
return 1;
}
