/*
ID: varunra2
LANG: C++
TASK: supertrees
*/
#include <bits/stdc++.h>
using namespace std;
#include "supertrees.h"
#ifdef DEBUG
#include "lib/debug.h"
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#define debug_arr(...) \
cerr << "[" << #__VA_ARGS__ << "]:", debug_arr(__VA_ARGS__)
#pragma GCC diagnostic ignored "-Wsign-compare"
//#pragma GCC diagnostic ignored "-Wunused-parameter"
//#pragma GCC diagnostic ignored "-Wunused-variable"
#else
#define debug(...) 42
#endif
#define EPS 1e-9
#define IN(A, B, C) assert(B <= A && A <= C)
#define INF (int)1e9
#define MEM(a, b) memset(a, (b), sizeof(a))
#define MOD 1000000007
#define MP make_pair
#define PB push_back
#define all(cont) cont.begin(), cont.end()
#define rall(cont) cont.end(), cont.begin()
#define x first
#define y second
const double PI = acos(-1.0);
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef map<int, int> MPII;
typedef multiset<int> MSETI;
typedef set<int> SETI;
typedef set<string> SETS;
typedef vector<int> VI;
typedef vector<PII> VII;
typedef vector<VI> VVI;
typedef vector<string> VS;
#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define trav(a, x) for (auto& a : x)
#define sz(x) (int)(x).size()
typedef pair<int, int> pii;
typedef vector<int> vi;
#pragma GCC diagnostic ignored "-Wsign-compare"
// util functions
int n;
VVI p;
VVI ret;
void dfs(int i, vector<bool>& vis, int bnd, VI& cmp) {
if (vis[i]) return;
vis[i] = true;
cmp.PB(i);
for (int ii = 0; ii < n; ii++) {
if (i == ii) continue;
if (p[i][ii] >= bnd) {
dfs(ii, vis, bnd, cmp);
}
}
}
bool isBad() {
trav(x, p) trav(y, x) if (y == 3) return false;
for (int i = 0; i < n; i++) {
if (p[i][i] != 1) return false;
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (p[i][j] != p[j][i]) return false;
}
}
vector<bool> vis(n, false);
for (int i = 0; i < n; i++) {
if (vis[i]) continue;
VI comp;
dfs(i, vis, 1, comp);
trav(x, comp) trav(y, comp) if (p[x][y] == 0) return false;
}
return true;
// change/update later
}
// void solve(VI& comp) {
// }
struct dsu {
VI par;
VI siz;
int n;
void init(int _n) {
n = _n;
par.resize(n);
siz.resize(n);
for (int i = 0; i < n; i++) {
par[i] = i;
siz[i] = 1;
}
}
bool ispar(int x) { return x == par[x]; }
int find(int x) {
while (par[x] != par[par[x]]) par[x] = par[par[x]];
return par[x];
}
bool same(int x, int y) { return find(x) == find(y); }
void merge(int x, int y) {
x = find(x);
y = find(y);
// if (siz[x] < siz[y]) swap(x, y);
par[y] = x;
siz[x] += siz[y];
}
};
void edge(int u, int v) {
// make an edge between u and v
if (u < 0 or v < 0 or u >= n or v >= n) return;
ret[u][v] = 1;
ret[v][u] = 1;
}
int buildcycle(VI& comp) {
// build a cycle, first element is the parent
if (sz(comp) == 0) return 1;
if (sz(comp) == 1) return 1;
if (sz(comp) == 2) return 0;
edge(comp[0], comp.back());
for (int i = 0; i < sz(comp) - 1; i++) {
edge(comp[i], comp[i + 1]);
}
return 1;
}
void buildtree(VI& comp) {
// build tree, first element is root
for (int i = 1; i < sz(comp); i++) {
edge(comp[0], comp[i]);
}
}
// void build(VVI& a) {
// // bruh
// // debug(a);
// debug("here");
// for (int i = 0; i < n; i++) {
// debug(i, a[i]);
// }
// }
int construct(VVI asdf) {
n = sz(asdf);
p = asdf;
ret.resize(n);
for (int i = 0; i < n; i++) {
ret[i].resize(n);
}
if (!isBad()) return 0;
dsu a;
a.init(n);
rep(i, 0, n) rep(j, 0, n) {
if (p[i][j] == 1 and !a.same(i, j)) {
a.merge(i, j);
}
}
rep(i, 0, n) {
if (!a.ispar(i)) {
ret[i][a.find(i)] = 1;
ret[a.find(i)][i] = 1;
}
}
VI b(n);
for (int i = 0; i < n; i++) {
if (a.ispar(i))
b[i] = i;
else
b[i] = -1;
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (p[i][j] == 2 and b[i] != b[j] and b[i] != -1 and b[j] != -1) {
int bb = b[i];
for (int k = 0; k < n; k++) {
if (b[k] == bb) b[k] = b[j];
}
}
}
}
for (int i = 0; i < n; i++) {
VI comp;
for (int j = 0; j < n; j++) {
if (b[j] == i) comp.PB(j);
}
int x = buildcycle(comp);
if (x == 0) return 0;
}
build(ret);
return 1;
}
// int main() {
// #ifndef ONLINE_JUDGE
// freopen("supertrees.in", "r", stdin);
// freopen("supertrees.out", "w", stdout);
// #endif
// cin.sync_with_stdio(0);
// cin.tie(0);
// int n;
// cin >> n;
// VVI vals(n, VI(n));
// for (int i = 0; i < n; i++) {
// for (int j = 0; j < n; j++) {
// cin >> vals[i][j];
// }
// }
// int x = construct(vals);
// debug(x);
// return 0;
// }
