import java.io.*; import java.util.*;
public class supertrees {
static class Pair implements Comparable<Pair>{
int v; int l0;
public Pair(int a, int b){
this.v=a; this.l0=b;
}
public int compareTo(Pair other){//Sort by l0 values
if(this.l0>other.l0)return 1;
if(this.l0<other.l0)return -1;
if(this.v<other.v)return -1;
if(this.v>other.v)return 1;
return 0;
}
}
/*
public static void main(String[] args) throws IOException {
// Tester code
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
int N=Integer.parseInt(br.readLine());
int[][] p=new int[N][N];
for (int i = 0; i < N; i++) {
StringTokenizer st=new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
p[i][j]=Integer.parseInt(st.nextToken());
}
}
System.out.println(construct(p));
}
*/
public static int construct(int[][] p){
int N=p.length;
int[][] b=new int[N][N];
int[] rank1=new int[N];//Consider the graph of 1-edges
int[] rank0=new int[N];//Graph of 1,2-edges
int[] par1=new int[N];
int[] par0=new int[N];
for (int i =0; i < N; i++) {
par1[i]=i; par0[i]=i;
}
int ii,jj;
for (int i = 0; i < N; i++) {
for (int j =0; j < N; j++) {
if(i==j)continue;
if(p[i][j]==1){
ii=find(i,par1); jj=find(j,par1);
if(ii!=jj){
if(rank1[ii]<rank1[jj]){
par1[ii]=jj;
}else if(rank1[ii]==rank1[jj]){
par1[ii]=jj; rank1[jj]++;
}else{
par1[jj]=ii;
}
}
ii=find(i,par0); jj=find(j,par0);
if(ii!=jj){
if(rank0[ii]<rank0[jj]){
par0[ii]=jj;
}else if(rank0[ii]==rank0[jj]){
par0[ii]=jj; rank0[jj]++;
}else{
par0[jj]=ii;
}
}
}else if(p[i][j]==2){
ii=find(i,par1); jj=find(j,par1);
if(ii==jj){//Deals with case i)
return 0;
}
ii=find(i,par0); jj=find(j,par0);
if(ii!=jj){
if(rank0[ii]<rank0[jj]){
par0[ii]=jj;
}else if(rank0[ii]==rank0[jj]){
par0[ii]=jj; rank0[jj]++;
}else{
par0[jj]=ii;
}
}
}else if(p[i][j]==3){
return 0;
}else{
ii=find(i,par0); jj=find(j,par0);
if(ii==jj)return 0;
}
}
}
//Now for every 1-2 component, we need to find number of 1-leaders
//That is the length of cycle. I lose if its length is 2 (length 1 is just a tree)
boolean[] done=new boolean[N];
int[] ans=new int[N];
for (int i = 0; i < N; i++) {
ii=find(i,par1);
if(!done[ii]){
jj=find(ii,par0);
ans[jj]++;
done[ii]=true;
}
}
//System.out.println(Arrays.toString(ans));
for (int i = 0; i < N; i++) {
if(ans[i]==2){
return 0;
}
}
TreeSet<Pair> leads=new TreeSet<>();//Include leaders of all 1-components
done=new boolean[N];
for (int i = 0; i < N; i++) {//1-graphs
ii=find(i,par1);
if(ii!=i){
b[i][ii]=1; b[ii][i]=1;
//Same component guys don't matter
}
//I want to insert every root of each par1 component exactly once
if(!done[ii]){
leads.add(new Pair(ii,find(ii,par0)));
}
}
int prevl=-1;
//Completes a cycle for a component
ArrayList<Integer> arl=new ArrayList<>();
for (Pair q: leads) {
//System.out.println(q.v+" "+q.l0+" "+prevv);
//System.out.println(q.v+" "+q.l0);
if(prevl!=q.l0){
if(arl.size()>0){
for (int i = 0; i < arl.size()-1; i++) {
b[arl.get(i)][arl.get(i+1)]=1;
b[arl.get(i+1)][arl.get(i)]=1;
}
b[arl.get(0)][arl.get(arl.size()-1)]=1;
b[arl.get(arl.size()-1)][arl.get(0)]=1;
arl=new ArrayList<>();
}
}
arl.add(q.v);
prevl=q.l0;
}
// System.out.println(arl);
if(arl.size()>0){
for (int i = 0; i < arl.size()-1; i++) {
b[arl.get(i)][arl.get(i+1)]=1;
b[arl.get(i+1)][arl.get(i)]=1;
}
b[arl.get(0)][arl.get(arl.size()-1)]=1;
b[arl.get(arl.size()-1)][arl.get(0)]=1;
}
//Last fill
//The leaders of every component forms a cycle as long as they're connected in the >=1 graph
for (int i = 0; i < N; i++) {
b[i][i]=0;
}
grader.build(b);
return 1;
}
public static int find(int x, int[] par){
if(par[x]==x)return x;
int ans=find(par[x],par);
par[x]=ans; return ans;
}
}
