// Author: caption_mingle
#include "bits/stdc++.h"
#include "supertrees.h"
using namespace std;
#define ln "\n"
#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define ll long long
const int mod = 1e9 + 7;
const int inf = 2e9;
struct DSU {
int n;
vector<int> par,sz;
DSU() {}
DSU(int n) : n(n) {
par.resize(n, 0);
sz.resize(n, 1);
for(int i = 1; i < n; i++) par[i] = i;
}
int find(int u) {
return u == par[u] ? u : par[u] = find(par[u]);
}
void join(int u, int v) {
u = find(u), v = find(v);
if(u == v) return;
if(sz[u] < sz[v]) swap(u, v);
sz[u] += sz[v];
par[v] = u;
}
};
int construct(vector<vector<int>> p) {
int n = sz(p);
vector<vector<int>> ans(n, vector<int>(n, 0));
DSU d(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]) d.join(i, j);
}
}
vector<vector<int>> gp(n);
for(int i = 0; i < n; i++) {
gp[d.find(i)].pb(i);
for(int j = 1; j < n; j++) {
if(d.find(i) == d.find(j) and p[i][j] == 0) return 0;
}
}
for(int i = 0; i < n; i++) {
if(sz(gp[i]) <= 1) continue;
bool check1 = 1;
if(sz(gp[i]) >= 3) {
for(int j = 0; j < sz(gp[i]); j++) {
int u = gp[i][j];
for(int k = j + 1; k < sz(gp[i]); k++) {
int v = gp[i][k];
for(int t = k + 1; t < sz(gp[i]); t++) {
int w = gp[i][t];
if(p[u][v] * p[v][w] * p[u][w] == 2) return 0;
if(p[u][v] * p[v][w] * p[u][w] != 1) check1 = 0;
}
}
}
} else if(p[gp[i][0]][gp[i][1]] == 2) return 0;
if(check1) {
for(int j = 1; j < sz(gp[i]); j++) {
ans[gp[i][j]][gp[i][j - 1]] = 1;
ans[gp[i][j - 1]][gp[i][j]] = 1;
}
continue;
}
int st = -1;
vector<bool> mark(n, 0);
for(int j = 0; j < sz(gp[i]); j++) {
int u = gp[i][j];
for(int k = j + 1; k < sz(gp[i]); k++) {
int v = gp[i][k];
if(p[u][v] == 2) {
st = u;
break;
}
}
if(st != -1) break;
}
vector<int> circle;
circle.pb(st);
mark[st] = 1;
while(1) {
bool ok = 0;
int cur = circle.back();
for(int j = 0; j < sz(gp[i]); j++) {
int u = gp[i][j];
if(mark[u]) continue;
ok = 1;
for(int v : circle) {
if(p[u][v] == 1) {
ok = 0;
break;
}
}
if(ok) {
circle.pb(u), mark[u] = 1;
break;
}
}
if(!ok) break;
}
if(sz(circle) < 3) return 0;
ans[circle[0]][circle.back()] = 1;
ans[circle.back()][circle[0]] = 1;
for(int j = 0; j < sz(circle); j++) {
int u = circle[j];
if(j > 0) {
ans[u][circle[j - 1]] = 1;
ans[circle[j - 1]][u] = 1;
}
for(int k = 0; k < sz(gp[i]); k++) {
int v = gp[i][k];
if(mark[v]) continue;
if(p[u][v] == 1) {
ans[u][v] = 1;
ans[v][u] = 1;
}
}
}
}
build(ans);
return 1;
}
