#include <bits/stdc++.h>
#include "supertrees.h"
#define ll long long
#define ld long double
#define sp ' '
#define en '\n'
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
using namespace std;
struct Dsu {
vector<int> p;
void Reset(int n) {
p.resize(n);
iota(p.begin(), p.end(), 0);
}
int Find(int x) {
if (x == p[x]) return x;
return p[x] = Find(p[x]);
}
void Unite(int x, int y) {
x = Find(x);
y = Find(y);
if (x == y) return;
p[y] = x;
}
};
int construct(vector<vector<int>> p) {
int n = p.size();
vector<vector<int>> ans(n, vector<int>(n));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (p[i][j] == 3) return 0;
}
}
Dsu all;
all.Reset(n);
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (p[i][j] > 0) all.Unite(i, j);
}
}
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (all.Find(i) == all.Find(j) && p[i][j] == 0) return 0;
}
}
vector<vector<int>> v(n);
for (int i = 0; i < n; i++) {
v[all.Find(i)].push_back(i);
}
vector<bool> alone(n, 1);
for (int z = 0; z < n; z++) {
if (v[z].size() <= 1) continue;
vector<int> a;
int sz = v[z].size();
for (int i = 0; i < sz; i++) a.push_back(v[z][i]);
Dsu d;
d.Reset(n);
for (int i = 0; i < sz; i++) {
for (int j = i + 1; j < sz; j++) {
if (p[a[i]][a[j]] == 1) {
d.Unite(a[i], a[j]);
alone[a[i]] = alone[a[j]] = 0;
}
}
}
for (int i = 0; i < sz; i++) {
for (int j = i + 1; j < sz; j++) {
if (d.Find(a[i]) == d.Find(a[j]) && p[a[i]][a[j]] == 2) return 0;
}
}
vector<vector<int>> vv(n);
vector<int> koji;
for (int i = 0; i < sz; i++) {
vv[d.Find(a[i])].push_back(a[i]);
}
for (int i = 0; i < sz; i++) {
if (d.Find(a[i]) == a[i]) koji.push_back(a[i]);
}
int ksz = koji.size();
for (int i = 0; i < ksz; i++) {
int x = koji[i];
int y = koji[(i + 1) % ksz];
if (x != y) ans[x][y] = ans[y][x] = 1;
if (alone[x] == 1) continue;
int sza = vv[x].size();
for (int j = 0; j < sza - 1; j++) {
int c1 = vv[x][j];
int c2 = vv[x][j + 1];
ans[c1][c2] = ans[c2][c1] = 1;
}
}
for (int i = 0; i < sz; i++) {
for (int j = i + 1; j < sz; j++) {
if (d.Find(a[i]) == d.Find(a[j]) && p[a[i]][a[j]] == 2) return 0;
else if (d.Find(a[i]) != d.Find(a[j]) && p[a[i]][a[j]] == 1) return 0;
}
}
}
build(ans);
return 1;
}
