import Prog1Tools.IOTools;
public class Faerb{  
 //
 //
 // Es wird eine optimale, d. h. mit
 // den wenigst moeglichen Farben, 
 // eines Graphen konstruiert. 
 //
 static int voropt ;  // Hier ist das vorlaeufige Optimum vermerkt. 
 //
 //   Zunaechst die Eingabeprozedur. 
 //
 //
 public static void Einlesen(int[][] graph, int n){ 
                               //
			       //
			       // Eingabe ist die Anzahl der Knoten. 
                               // Ausgabe die Adjazenzmatrix des Graphen. 
                               //
                               //
                               //
 for (int i = 0; i < n; i++) {  // i geht die Zeilen lang. 
    //
    for (int j = i; j < n; j++) { // j geht die Spalten lang. 
    //     
    if (i == j) {
    graph[i][i] = 0;
    continue; }
    //
    graph[i][j] = IOTools.readInteger(" Kante " + i + "  " + j + 
                                           " einlesen  ");
    //
    graph[j][i] = graph[i][j];
    }
   }
 }
 //
 //  Der Loesungsraum ist die Menge aller
 //  Abbildungen F: {0,.. n-1} --> {0,1, ..., n-1}
 //  die jedem Knoten eine Farbe zuordnen. Nach Vorueberlegung
 //  reicht es, fuer Knoten i die Farben 0,1,2,3, ..., nur bis i
 //  auszuprobieren.
 //
 //
public static void Faerb(int[][] graph,  int[] F , 
                         int[] Fvoropt,  int knoten) {  
                                    // 
				    // Eine optimale Faerbung von graph. 
                                    // F die partielle Faerbung,
                                    // knoten der Knoten, der dran ist,
                                    // anz Anzahl der verbrauchten Farben. 
                                    //
                 //
int anz = 0;     //Hier wird die Anzahl der Farben ermittelt in F ermittelt.  
                 // 
int[] Test = new int[F.length];
//
for (int i = 0; i < knoten; i++) Test[F[i]] = 1;
//
//
for (int i = 0; i < knoten; i++) if (Test[i] > 0) anz = anz + 1;
// 
if (knoten == F.length && anz < voropt)  { // Eine neue Faerbung. 
    voropt = anz; 
    for (int  i = 0; i < F.length; i++)		  
	Fvoropt[i] = F[i]; 
	return; 
	}		  
//
if (anz >= voropt) return;    // Es hat sowieso keinen Sinn mehr weiterzumachen.  
//			  
naeFar: for (int i = 0; i <= knoten; i++) { //Testen die Farben 0,1,2,...knoten.
         // 
	  for (int j = 0; j < knoten ; j++)  { // Gucken, ob Farbe passt. 
            if (graph[knoten][j] == 1 && F[j] == i) continue naeFar; }
            //
	    F[knoten] = i; 
	    Faerb(graph, F, Fvoropt, knoten + 1); 
	    //
	    }                                  
 }
 //
 //
 //
 public static void Ausgabe(int[ ] F) {
 int i = 0;
 while (i < F.length) {
    System.out.println("Farbe von  " + i + " ist " +  F[i]);
    i++; 
    }     
 }     
  //
  
  //
  //
  public static void main(String[] args) {
  //
  int groesse; 
  int[] F, Fvoropt;
  int[][] graph;
  //  
  //
  groesse = IOTools.readInteger("groesse einlesen " );
  //
  voropt = groesse ;
  //
  graph = new int[groesse][groesse];
  //
  //
  Einlesen( graph, groesse);
  //
  F= new int[groesse];
  //
  Fvoropt = new int[groesse];
  // 
  for (int i = 0; i < Fvoropt.length; i++) 
      Fvoropt[i] = i;
  //
  Faerb(graph, F, Fvoropt, 0);
  
  Ausgabe(Fvoropt); 
    } 
  }