import Prog1Tools.IOTools;
public class DrFaeRa{  
 //
 //
 //   Hier wird festgestellt,
 //   ob ein Graph gegeben durch
 //   seine Adjazenzmatrix, 
 //   Eingabe als Zufallsgraph, p/n,
 //   p per Hand eingegeben
 //   3-faerbbar ist. 
 //
 //   Zunaechst die Eingabeprozedur. 
 //
 //
 public static void Einlesen(int[][] graph, double c, int n){ // Eingabe ist die Anzahl der Knoten. 
                                                             //  Produktion der Adjazenzmatrix des Graphen. 
 int anz = 0;//
 //
 //
 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; }
    //
    if (Math.random() * n <= c) {
    graph[i][j] = 1; 
    anz = anz +1;}
    //
    graph[j][i] = graph[i][j];
    }
   }
    System.out.println("Anzahl Kanten ist  " + anz);
 }
 //
 //
 //
 //  Der Loesungsraum ist die Menge aller
 //  Abbildungen F: {0,.. n-1} --> {1,2,3}
 //  die jedem Knoten eine Farbe zuordnen. 
 //   
 //
 //
 //
public static boolean Faerb(int[][] graph,  int[] F ,  int knoten) {  
                                    // Bestimmt eine zulaessige 3-Faerbung 
				    // von graph.
                                    //
boolean test= false; 
//
if (knoten == F.length)  return true; //
                                      //
				      //Eine 3-Faerbung ist gefunden.
                                      //Schluss. 
                                      //
                                      //
naeFar: for (int i = 1; i <= 3; i++) { //Testen die Farben 1,2,3.
         // 
	  for (int j = 0; j < knoten ; j++)  { // Gucken, ob Farbe passt. 
            if (graph[knoten][j] == 1 && F[j] == i) continue naeFar; }
            //
	    F[knoten] = i;
	    test = Faerb(graph, F, knoten + 1);
	    if (test) return true; } 
            //
 return false ;// Hier ist test sowieso == false
      }
 //
 //
 //
 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;
  double c;
  int[] F;
  int[][] graph;
  boolean test;//  
  //
  groesse = IOTools.readInteger("groesse einlesen " );
  //
  c = IOTools.readDouble("c einlesen ");
  //
  graph = new int[groesse][groesse];
  //
  //
  Einlesen( graph, c, groesse);
  //
  F= new int[groesse];
  // 
  test = Faerb(graph, F, 0);
  //
  if (test) {System.out.println("3-faerbbar");
            Ausgabe(F);}//
      else System.out.println("Nicht 3-faerbbar"); 
              } 
  }