#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;
for (int i : comp) for (int j : comp) if (p[i][j] != 1) return 0;
}
seen.assign(n, 0);
for (int c = 0; c < n; c++) {
set<int> disc;
auto dfs2 = [&](auto dfs, int u) -> void {
if (seen[u]) return;
seen[u] = 1;
color2[u] = c;
if (root[u] >= 0) disc.insert(root[u]);
else disc.insert(u);
for (int v = 0; v < n; v++) if (p[u][v]) dfs(dfs, v);
};
dfs2(dfs2, c);
vi comp(disc.begin(), disc.end());
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;
}
