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

public class GColLite {

    int n, colours;
    long nodes, checks;
    boolean[][] adjacent;
    int[] v; // v[i] is value assigned to the vertex v[i]
    
    GColLite(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]) checks++;
	return !adjacent[i][j] || v[i] != v[j];
    }
    //
    // If adjacent, is v[i] consistent with v[j]?
    //
    
    boolean solve(){
	return expand(0);
    }

    boolean expand(int i){
	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);
	}
	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 {
	 
	GColLite gcol = new GColLite(args[0]);
	gcol.colours = Integer.parseInt(args[1]);
	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();
    }
}