import java.io.*;

class GraphColoring {
    int[][] adjacencyMatrix;   // adjacencyMatrix[i][j] = 1 if edge exists between i and j
    int    numVertices;        // total number of vertices in the graph
    int    numEdges;           // total number of edges
    int    numColors;          // maximum number of colours allowed (m)
    int[]  colorAssignment;    // colorAssignment[v] = colour assigned to vertex v

    /** Reads the graph from user input */
    void readGraph() throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        System.out.println("Enter the number of vertices:");
        numVertices       = Integer.parseInt(reader.readLine());
        adjacencyMatrix   = new int[numVertices + 1][numVertices + 1];
        colorAssignment   = new int[numVertices + 1];

        System.out.println("Enter the number of edges:");
        numEdges = Integer.parseInt(reader.readLine());

        // Initialise all edges to 0 (no connection)
        for (int i = 1; i <= numVertices; i++)
            for (int j = 1; j <= numVertices; j++)
                adjacencyMatrix[i][j] = 0;

        // Read each edge and mark it in the adjacency matrix (undirected)
        for (int i = 1; i <= numEdges; i++) {
            System.out.println("Enter edge " + i + " (vertex u then vertex v):");
            int vertexU = Integer.parseInt(reader.readLine());
            int vertexV = Integer.parseInt(reader.readLine());
            adjacencyMatrix[vertexU][vertexV] = 1;
            adjacencyMatrix[vertexV][vertexU] = 1;  // undirected graph
        }

        System.out.println("Enter the number of colours (m):");
        numColors = Integer.parseInt(reader.readLine());
    }

    /**
     * Recursively assigns colours to vertices using backtracking.
     * Prints each valid complete colouring found.
     *
     * @param currentVertex the vertex currently being coloured (1-indexed)
     */
    void mColoring(int currentVertex) {
        do {
            // Try the next available colour for currentVertex
            nextColor(currentVertex);

            if (colorAssignment[currentVertex] == 0) {
                // No valid colour exists for this vertex -- backtrack
                break;
            }

            if (currentVertex == numVertices) {
                // All vertices coloured -- print this valid solution
                for (int i = 1; i <= numVertices; i++) {
                    System.out.print(colorAssignment[i] + "   ");
                }
                System.out.println();
            } else {
                // Move to the next vertex
                mColoring(currentVertex + 1);
            }
        } while (true);
    }

    /**
     * Finds the next valid colour for the given vertex by incrementing
     * its current colour and checking for conflicts with adjacent vertices.
     * Sets colorAssignment[vertex] to 0 if no valid colour is found.
     *
     * @param vertex the vertex whose colour is being determined
     */
    void nextColor(int vertex) {
        do {
            // Increment to the next candidate colour
            colorAssignment[vertex] = (colorAssignment[vertex] + 1) % (numColors + 1);

            if (colorAssignment[vertex] == 0) {
                // Exhausted all colours -- signal backtrack
                break;
            }

            // Check if any adjacent vertex already uses this colour
            boolean conflictFound = false;
            for (int neighbour = 1; neighbour <= numVertices; neighbour++) {
                if (adjacencyMatrix[vertex][neighbour] != 0 &&
                    colorAssignment[neighbour] == colorAssignment[vertex]) {
                    conflictFound = true;
                    break;
                }
            }
            if (!conflictFound) break;  // found a valid colour
        } while (true);
    }
}

class GraphColoringMain {
    public static void main(String[] args) throws IOException {
        GraphColoring gc = new GraphColoring();
        gc.readGraph();
        gc.mColoring(1);  // start colouring from vertex 1
    }
}