#include <bits/stdc++.h>
void build(std::vector <std::vector <int>> b);
void ff1(int node, int n, std::vector <std::vector <int>>& p, std::vector <std::vector <int>>& col, std::vector <bool>& vis) {
if (vis[node]) return;
vis[node] = true;
col.back().push_back(node);
for (int i = 0; i < n; i++) {
if (p[node][i] == 1) {
ff1(i, n, p, col, vis);
}
}
}
void ff2(int node, int n, std::vector <std::vector <int>>& p, std::vector <std::vector <int>>& col, std::vector <bool>& vis) {
if (vis[node]) return;
vis[node] = true;
col.back().push_back(node);
for (int i = 0; i < n; i++) {
if (p[node][i] == 2) {
ff2(i, n, p, col, vis);
}
}
}
void dfs(int node, int n, std::vector <bool>& vis, std::vector <int>& cnt, std::vector <std::vector <int>>& g) {
if (vis[node]) return;
vis[node] = true;
cnt[node]++;
for (int x : g[node]) {
dfs(x, n, vis, cnt, g);
}
vis[node] = false;
}
int construct(std::vector <std::vector <int>> p) {
std::vector <std::vector <int>> ep(p);
int n = p.size();
std::vector <std::vector <int>> ocol;
for (int i = 0; i < n; i++) {
static std::vector <bool> vis(n, false);
if (vis[i]) continue;
for (int j = i + 1; j < n; j++) {
if (p[i][j] == 1) {
ocol.push_back({ });
ff1(i, n, p, ocol, vis);
break;
}
}
}
for (auto& v : ocol) {
for (size_t i = 1; i < v.size(); i++) {
for (int j = 0; j < n; j++) {
p[v[i]][j] = p[j][v[i]] = 0;
}
p[v[i]][v[i]] = 1;
}
}
std::vector <std::vector <int>> tcol;
for (int i = 0; i < n; i++) {
static std::vector <bool> vis(n, false);
if (vis[i]) continue;
for (int j = i + 1; j < n; j++) {
if (p[i][j] == 2) {
tcol.push_back({ });
ff2(i, n, p, tcol, vis);
break;
}
}
}
std::vector <std::vector <int>> ans(n, std::vector <int> (n, 0));
for (auto& v : ocol) {
for (size_t i = 0; i < v.size() - 1; i++) {
ans[v[i]][v[i + 1]] = ans[v[i + 1]][v[i]] = 1;
}
}
for (auto& v : tcol) {
for (size_t i = 0; i < v.size() - 1; i++) {
ans[v[i]][v[i + 1]] = ans[v[i + 1]][v[i]] = 1;
}
ans[v[0]][v.back()] = ans[v.back()][v[0]] = 1;
}
std::vector <std::vector <int>> adj(n);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (ans[i][j]) adj[i].push_back(j);
}
}
for (int i = 0; i < n; i++) {
std::vector <bool> vis(n, false);
std::vector <int> cnt(n, 0);
dfs(i, n, vis, cnt, adj);
for (int j = 0; j < n; j++) {
if (ep[i][j] != cnt[j]) return 0;
}
}
build(ans);
return 1;
}
