#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);
vi color1(n), color2(n);
for (int c = 0; c < n; c++) {
vi comp;
auto dfs1 = [&](auto dfs, int u) -> void {
if (seen[u]) return;
color1[u] = c;
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;
color2[u] = c;
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;
}
for(int i = 0; i < n; i++) for (int j = 0; j < n; j++) {
if (p[i][j] == 0 && color2[i] == color2[j]) return 0;
if (p[i][j] == 1 && color1[i] != color1[j]) return 0;
if (p[i][j] == 2 && (color1[i] == color1[j] || color2[i] != color2[j])) return 0;
}
build(ans);
return 1;
}
