#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();
for(int i = 0; i < n; i++) for (int j = 0; j < n; j++) if (p[i][j] == 3) return 0;
vvi ans(n, vi(n));
vi seen(n), root(n, -1);
for (int c = 0; c < n; c++) {
vi comp;
auto dfs1 = [&](auto dfs, int u) -> void {
if (seen[u]) return;
seen[u] = 1;
root[u] = c;
comp.push_back(u);
for (int v = 0; v < n; v++) if (p[u][v] == 1) dfs(dfs, v);
};
dfs1(dfs1, c);
for (int i = 0; i < (int)comp.size()-1; i++) ans[comp[i]][comp[i+1]] = ans[comp[i+1]][comp[i]] = 1;
}
seen.assign(n, 0);
for (int c = 0; c < n; c++) {
set<int> roots;
vi all;
vi twos;
auto dfs2 = [&](auto dfs, int u) -> void {
if (seen[u]) return;
seen[u] = 1;
all.push_back(u);
roots.insert(root[u]);
bool two = 0;
for (int v = 0; v < n; v++) if (p[u][v] == 2) two = 1;
for (int v = 0; v < n; v++) if (u != v && p[u][v] == 1) two = 0;
if (two) twos.push_back(u);
for (int v = 0; v < n; v++) if (p[u][v]) dfs(dfs, v);
};
dfs2(dfs2, c);
for (int i = 0; i < (int)twos.size()-1; i++) ans[twos[i]][twos[i+1]] = ans[twos[i+1]][twos[i]] = 1;
vi comp(roots.begin(), roots.end());
for (int i : twos) comp.push_back(i);
if (comp.size() == 2) return 0;
if (comp.size() <= 1) continue;
comp.push_back(comp[0]);
for (int i = 0; i < (int)comp.size()-1; i++) ans[comp[i]][comp[i+1]] = ans[comp[i+1]][comp[i]] = 1;
}
build(ans);
return 1;
}
