#include "supertrees.h"
#include <bits/stdc++.h>
#define ALL(X) begin(X), end(X)
namespace {
using i64 = long long;
using namespace std;
template <class T>
using vec = vector<T>;
template <class T>
istream& operator>>(istream& is, vec<T>& X) {
for (auto& x : X) {
is >> x;
}
return is;
}
template <class T>
constexpr T infty = 0;
template <>
constexpr int infty<int> = 1'000'000'000;
template <>
constexpr i64 infty<i64> = 1'000'000'000'000'000'000;
struct Unionfind {
vec<int> p;
Unionfind(int N) : p(N, -1) {};
int find(int x) {
return p[x] < 0 ? x : (p[x] = find(p[x]));
}
void join(int x, int y) {
if ((x = find(x)) == (y = find(y))) {
return;
}
if (p[x] > p[y]) {
swap(x, y);
}
p[x] += exchange(p[y], x);
}
bool same(int x, int y) {
return find(x) == find(y);
}
};
}
int construct(std::vector<std::vector<int>> p) {
int N = size(p);
Unionfind uf(N);
for (int i = 0; i < N; i++) {
for (int j = i + 1; j < N; j++) {
if (p[i][j] == 3) {
return 0;
}
if (p[i][j] == 1) {
uf.join(i, j);
}
}
}
for (int i = 0; i < N; i++) {
for (int j = i + 1; j < N; j++) {
if (p[i][j] != 1 && uf.same(i, j)) {
return 0;
}
}
}
vec<int> rep(N);
vec<vec<int>> ccs(N);
for (int i = 0; i < N; i++) {
rep[i] = uf.find(i);
ccs[uf.find(i)].emplace_back(i);
}
fill(ALL(uf.p), -1);
for (int i = 0; i < N; i++) {
for (int j = i + 1; j < N; j++) {
if (p[i][j] == 3) {
return 0;
}
if (p[i][j] == 2) {
uf.join(i, j);
}
}
}
for (int i = 0; i < N; i++) {
for (int j = i + 1; j < N; j++) {
if (p[i][j] == 0 && uf.same(i, j)) {
return 0;
}
}
}
vec<int> rep2(N);
vec<vec<int>> ccs2(N);
for (int i = 0; i < N; i++) {
rep2[i] = uf.find(i);
ccs2[uf.find(i)].emplace_back(i);
}
for (int i = 0; i < N; i++) {
for (int j = 1; j < (int)size(ccs[i]); j++) {
if (rep2[ccs[i][j - 1]] != rep2[ccs[i][j]]) {
return 0;
}
}
}
vec<vec<int>> ans(N, vec<int>(N));
for (int i = 0; i < N; i++) {
if (size(ccs[i]) == 1) {
continue;
}
for (int j = 1; j < (int)size(ccs[i]); j++) {
int u = ccs[i][j - 1];
int v = ccs[i][j];
ans[u][v] = ans[v][u] = 1;
}
}
for (int i = 0; i < N; i++) {
if (size(ccs2[i]) == 1) {
continue;
}
for (auto& x : ccs2[i]) {
x = rep[x];
}
sort(ALL(ccs2[i]));
ccs2[i].resize(unique(ALL(ccs2[i])) - begin(ccs2[i]));
if (size(ccs2[i]) == 2) {
return 0;
}
assert(size(ccs2[i]) != 1);
int n = size(ccs2[i]);
for (int j = 0; j < n; j++) {
int u = ccs2[i][j];
int v = ccs2[i][(j + 1) % n];
ans[u][v] = ans[v][u] = 1;
}
}
build(ans);
return 1;
}
