#ifdef LOCAL
#else
#include "supertrees.h"
#endif
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#ifdef LOCAL
#define dbg(...) debug(#__VA_ARGS__, __VA_ARGS__);
#else
#define dbg(...) 17;
#endif
template<typename T, typename S> ostream& operator << (ostream &os, const pair<T, S> &p) { return os << "(" << p.first << ", " << p.second << ")"; }
template<typename C, typename T = decay<decltype(*begin(declval<C>()))>, typename enable_if<!is_same<C, string>::value>::type* = nullptr>
ostream& operator << (ostream &os, const C &c) { bool f = true; os << "{"; for (const auto &x : c) { if (!f) os << ", "; f = false; os << x; } return os << "}"; }
template<typename T> void debug(string s, T x) { cerr << s << " = " << x << "\n"; }
template<typename T, typename... Args> void debug(string s, T x, Args... args) { cerr << s.substr(0, s.find(',')) << " = " << x << " | "; debug(s.substr(s.find(',') + 2), args...); }
#ifdef LOCAL
bool build(vector<vector<int>> p) {
return true;
}
#else
#endif
int construct(vector<vector<int>> p) {
int n = p.size();
vector<vector<int>> res(n, vector<int>(n, 0));
vector<bool> vis(n);
auto ae = [&](int u, int v) {
res[u][v] = 1;
res[v][u] = 1;
};
auto make_cycle = [&](vector<int>& v) {
for (int i = 0; i < v.size(); i++) {
ae(v[i], v[(i + 1) % v.size()]);
}
};
auto make_triple = [&](vector<int>& v) {
make_cycle(v);
ae(v[0], v[2]);
};
auto make_chain = [&](vector<int>& v) {
for (int i = 0; i < v.size() - 1; i++) {
ae(v[i], v[i + 1]);
}
};
for (int i = 0; i < n; i++) {
if (vis[i]) continue;
vector<int> comp;
function<void(int)> dfs_comp = [&](int src) {
vis[src] = true;
comp.push_back(src);
for (int nxt = 0; nxt < n; nxt++) {
if (p[src][nxt] == 0 || vis[nxt]) continue;
dfs_comp(nxt);
}
};
dfs_comp(i);
int sz = comp.size();
vector<int> overall(4);
vector<int> one;
vector<int> other;
for (int x: comp) {
vector<int> cnt(4);
for (int y: comp) {
if (x == y) continue;
cnt[p[x][y]]++;
overall[p[x][y]]++;
}
if (cnt[0]) {
return 0;
}
if (cnt[1] == 0) {
other.push_back(x);
} else {
one.push_back(x);
}
}
if (overall[0] || overall[2] && overall[3]) {
return 0;
}
if (overall[2] == 0 && overall[3] == 0) {
vector<int> big;
for (int x: one) big.push_back(x);
for (int x: other) big.push_back(x);
make_chain(big);
continue;
}
vector<vector<int>> chains;
for (int x: one) {
bool done = false;
for(auto& y: chains) {
bool ok = false;
for (int z: y) {
if (p[x][z] != 1) {
ok = true;
break;
}
}
if (ok == false) {
y.push_back(x);
done = true;
break;
}
}
if (done == false) {
chains.push_back(vector<int>(0));
chains.back().push_back(x);
}
}
for (auto& c: chains) {
for (int x: c) {
for (int y: c) {
if (p[x][y] != 1) {
return 0;
}
}
}
}
for (int j = 0; j < chains.size(); j++) {
for (int k = j + 1; k < chains.size(); k++) {
for (int x: chains[j]) {
for (int y: chains[k]) {
if (p[x][y] == 1) {
return 0;
}
}
}
}
}
int cycle = chains.size() + other.size();
if (overall[2]) {
if (cycle < 3) {
return 0;
}
for (auto x: chains) {
other.push_back(x[0]);
make_chain(x);
}
make_cycle(other);
} else if (overall[3]) {
return 0;
} else {
vector<int> big;
for (int x: one) big.push_back(x);
for (int x: other) big.push_back(x);
make_chain(big);
}
}
build(res);
return 1;
}
#ifdef LOCAL
int main() {
freopen("file.in", "r", stdin);
string line; cin >> line;
int n; cin >> n;
vector<vector<int>> p(n, vector<int>(n, 0));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> p[i][j];
}
}
cout << construct(p) << '\n';
return 0;
}
#else
#endif
