#include <bits/stdc++.h>
#include <vector>
#define MAX 1005
using namespace std;
vector<int>team_type1[MAX];
int N;
int nbt[MAX];
bool vis[MAX];
vector<vector<int>>answer;
void myfill2(int nod,vector<int>&nodes,vector<int>&put_val,vector<vector<int>>&p)
{
put_val.push_back(nod);
vis[nod]=1;
for(auto el : nodes)
if(p[nod][el]==1 && !vis[el])
myfill2(el,nodes,put_val,p);
}
bool solve_connected_component(vector<int>&nodes,vector<vector<int>>&p)
{
vector<int>put_val;
int i;
int primul=-1,ult=-1;
int cnt=0;
for(auto el : nodes)
if(!vis[el])
{
++cnt;
myfill2(el,nodes,put_val,p);
for(auto el1 : put_val)
for(auto el2 : put_val)
if(p[el1][el2]==2)
return 0;
for(i=1;i<put_val.size();++i)
answer[put_val[i-1]][put_val[i]]=answer[put_val[i]][put_val[i-1]]=1;
if(primul>-1)
{
answer[ult][put_val[0]]=answer[put_val[0]][ult]=1;
ult=put_val[0];
}
else
primul=ult=put_val[0];
put_val.clear();
}
/// VERIFICA CNT SA NU FIE 2
if(cnt==2)
return 0;
if(primul!=ult)
answer[primul][ult]=answer[ult][primul]=1;
return 1;
}
void myfill(int nod,vector<vector<int>>&path,int nbteam)
{
team_type1[nbteam].push_back(nod);
nbt[nod]=nbteam;
int i;
for(i=0;i<N;++i)
if(!nbt[i] && path[i][nod])
myfill(i,path,nbteam);
}
void debug()
{
int i,j;
for(i=0;i<N;++i){
for(j=0;j<team_type1[i].size();++j)
cout<<team_type1[i][j]<<' ';
cout<<'\n';
}
}
bool check_type_1(vector<vector<int>>&p)
{
int i,j;
for(i=0;i<N;++i)
for(j=0;j<N;++j)
if(!p[i][j] && nbt[i]==nbt[j])
return 0;
return 1;
}
void build(vector<vector<int>>b);
int construct(vector<vector<int>>p)
{
int i,j;
N=p[0].size();
for(i=0;i<N;++i)
for(j=0;j<N;++j)
if(p[i][j]==3)
return 0;
answer.resize(N);
for(i=0;i<N;++i)
answer[i].resize(N);
int team=0;
for(i=0;i<N;++i)
if(!nbt[i])
myfill(i,p,++team);
if(!check_type_1(p))
return 0;
for(i=1;i<=team;++i)
if(!solve_connected_component(team_type1[i],p))
return 0;
build(answer);
return 1;
}
/*
int main()
{
int NN;
cin>>NN;
vector<vector<int> >mat;
mat.resize(NN);
int i;
for(i=0;i<NN;++i)
mat[i].resize(NN);
int j;
for(i=0;i<NN;++i)
for(j=0;j<NN;++j)
cin>>mat[i][j];
cout<<construct(mat);
return 0;
}
*/
