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

public class GCol {

    int n, colours;
    long nodes, checks;
    boolean[][] adjacent;
    int[] v; // v[i] is value assigned to the vertex v[i]
    boolean trace;
    
    GCol(String fname) throws IOException {
	Scanner sc = new Scanner(new File(fname));
	n = sc.nextInt();
	adjacent = new boolean[n][n];
	v = new int[n];
	while (sc.hasNext()){	  
	    int i = sc.nextInt() - 1;
	    int j = sc.nextInt() - 1; 
	    adjacent[i][j] = adjacent[j][i] = true;
	}
	sc.close();
    }

    boolean consistent(int i,int j){
	if (!adjacent[i][j]) return true;
	checks++;
	if (trace)
	    System.out.println("check(v["+ (i+1) +"]="+ v[i] +",v["+ (j+1) +"]="+ v[j] +") -> "+
			       (v[i] != v[j]));
	return v[i] != v[j];
    }
    //
    // If adjacent, is v[i] consistent with v[j]?
    //
    
    boolean solve(){
	return expand(0);
    }

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

    void stats(){
	System.out.println(checks +" checks and "+ nodes +" nodes");
    }

     public static void main(String[] args)  throws IOException {
	 
	GCol gcol = new GCol(args[0]);
	gcol.colours = Integer.parseInt(args[1]);
	gcol.trace = args.length > 2;
	if (gcol.solve()){
	    System.out.print("sol: ");
	    for (int i=0;i<gcol.n;i++) System.out.print(gcol.v[i]);
	    System.out.println();
	}
	else System.out.println("false");
	gcol.stats();
    }
}