#include "supertrees.h"
#include <bits/stdc++.h>
#define pb push_back
#define pf push_front
using namespace std;
#define F first
#define S second
typedef long long ll;
#define pii pair <int, int>
#define pll pair <ll, ll>
typedef long double ld;
const ll N = 1000 + 100, M = 4096 + 10, len = 21, inf = 1e18;
const ll mod = 1e9 + 7;
vector <int> q[N], g[N];
vector<vector<int>> ans;
vector <int> c, ml;
bool was[N], op[N];
void dfs1(int v){
was[v] = true;
c.pb(v);
for(auto u : q[v]){
if(was[u] == true) continue;
dfs1(u);
}
for(auto u : g[v]){
if(was[u] == true) continue;
dfs1(u);
}
}
void dfs2(int v){
op[v] = true;
ml.pb(v);
for(auto u : g[v]){
if(op[u]) continue;
dfs2(u);
}
}
// void build(vector<vector<int>> p){
// for(auto u : p){
// for(auto v : u){
// cout << v << " ";
// }
// cout << endl;
// }
// }
int construct(vector<vector<int>> p) {
int n = p.size();
bool can = true;
for (int i = 0; i < n; i++) {
vector<int> row;
row.resize(n);
ans.push_back(row);
}
// if(n <= 3){
// build(ans);
// return 1;
// }
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(i == j) continue;
if(p[i][j] == 2) q[i].pb(j);
if(p[i][j] == 1) g[i].pb(j);
}
}
//cout << "was\n";
for(int i = 0; i < n; i++){
if(was[i] == false){
dfs1(i);
vector <int> nw;
for(auto u : c){
if(op[u] == false){
dfs2(u);
for(int j = 1; j < (int)ml.size(); j++){
ans[ml[j]][ml[j - 1]] = ans[ml[j - 1]][ml[j]] = 1;
}
for(int j = 0; j < (int)ml.size(); j++){
for(int k = 0; k < (int)ml.size(); k++){
if(p[ml[j]][ml[k]] == 0) can = false;
}
}
nw.pb(ml[0]);
ml.clear();
}
}
c.clear();
if((int)nw.size() == 1) continue;
if((int)nw.size() == 2){
can = false;
continue;
}
for(int j = 1; j < (int)nw.size(); j++){
ans[nw[j]][nw[j - 1]] = ans[nw[j - 1]][nw[j]] = 1;
}
ans[nw[(int)nw.size() - 1]][nw[0]] = ans[nw[0]][nw[(int)nw.size() - 1]] = 1;
for(int j = 0; j < (int)nw.size(); j++){
for(int k = 0; k < (int)nw.size(); k++){
if(p[nw[j]][nw[k]] == 0) can = false;
}
}
}
}
if(can) build(ans);
return can;
}
/*
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
vector<vector<int>> p;
int n;
cin >> n;
for(int i = 0, x; i < n; i++){
vector <int >cur;
for(int j = 0; j < n; j++){
cin >> x;
cur.pb(x);
}
p.pb(cur);
}
construct(p);
return 0;
}
*/
