import java.util.*;
import java.io.*;

public class CrystalMaze {

    int n, nodes;
    boolean[][] adjacent;
    int[] v; // v[i] is value assigned to the vertex v[i]
    
    CrystalMaze(int n,boolean[][] adjacent){
	this.n = n;
	v = new int[n];
	this.adjacent = adjacent;
    }

    boolean consistent(int i,int j){
	return v[i] != v[j] &&
	    (!adjacent[i][j] || adjacent[i][j] && Math.abs(v[i] - v[j]) > 1);
    }
    //
    // Is v[i] consistent with v[j]?
    //
    
    boolean solve(){
	return expand(0);
    }

    boolean expand(int i){	
	if (i == n) return true; // everything assigned
	nodes++;
	boolean consistent = false;
	for (int j=0;j<n && !consistent;j++){ // find a consistent value j for v[i]
	    consistent = true;
	    v[i] = j;
	    for (int k=0;k<i && consistent;k++) // check backwards against current instantiations
		 consistent = consistent(i,k);
	    consistent = consistent && expand(i+1);
	}
	return consistent;
    }
    //
    // A backward checking chronological backtracker ... BT
    //
}