#include <bits/stdc++.h>
#define PB push_back
#define ST first
#define ND second
#define _ ios_base::sync_with_stdio(0); cin.tie(0);
//mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
using namespace std;
using ll = long long;
using pi = pair<int,int>;
using vi = vector<int>;
const int nax = 1000 + 10;
int n;
vi V1[nax], V2[nax];
bool done1[nax], done2[nax];
vi act = {}, cyc = {};
bool ont[nax];
vector<vi>g;
vi tmp[nax];
void build(vector<vi> b);
void dfs1(int x) {
done1[x] = 1;
act.PB(x);
for(int nbh : V1[x]) if(!done1[nbh]) {
dfs1(nbh);
}
}
void dfs2(int x) {
done2[x] = 1;
act.PB(x);
for(int nbh : V2[x]) if(ont[nbh] && !done2[nbh]) {
dfs2(nbh);
}
}
int construct(vector<vi>p) {
n = (int)p.size();
g.resize(n);
for(int i = 0; i < n; ++i) {
g[i].resize(n);
for(int j = 0; j < n; ++j) {
if(p[i][j] == 3) {
return 0;
}
if(p[i][j] == 1) {
V1[i].PB(j);
V1[j].PB(i);
} else if(p[i][j] == 2) {
V2[i].PB(j);
V2[j].PB(i);
}
}
}
for(int i = 0; i < n; ++i) {
if(!done1[i]) {
act = {};
dfs1(i);
ont[i] = 1;
tmp[i] = act;
for(int x : act) {
for(int y : act) {
if(p[x][y] != 1) return 0;
}
}
cyc.PB(i);
int a = i;
for(int x : act) {
if(x != a) {
g[x][a] = g[a][x] = 1;
}
}
}
}
for(int x : cyc) {
if(!done2[x]) {
act = {};
dfs2(x);
if((int)act.size() ==1 ) continue;
for(int x1 : act) {
for(int y : act) {
if(x1 != y) {
for(int y1 : tmp[y]) {
for(int x2 : tmp[x1]) {
if(p[x2][y1] != 2) {
return 0;
}
}
}
}
}
}
for(int j = 1; j < (int)act.size(); ++j) {
g[act[j]][act[j - 1]] = g[act[j - 1]][act[j]] = 1;
}
g[act[0]][act.back()] = g[act.back()][act[0]] = 1;
}
}
//~ for(int i = 0; i < n; ++i) {
//~ cout << ont[i] << " ";
//~ for(int j = 0; j < n; ++j) {
//~ cout << g[i][j] << " ";
//~ }
//~ cout << "\n";
//~ }
build(g);
return 1;
}
//~ int main() {
//~ cout << construct({{1, 1, 2, 2}, {1, 1, 2, 2}, {2, 2, 1, 2}, {2, 2, 2, 1}});
//~ }
