import java.util.ArrayList;
import java.util.Scanner;

public class MaxComponent
{
    private static int countVer;
    private static int countEdge;


    private static class Vertex {
        ArrayList<Integer> edge = new ArrayList<>();
        int visit;
        int numComp;
    }

    private static void visitVertex(Vertex[] nodes, Vertex v, int comp) {
        v.visit = 1;
        v.numComp = comp;
        (countVer)++;
        (countEdge) += v.edge.size();
        for(Integer u : v.edge){
            if(nodes[u].visit == 0)
                visitVertex(nodes, nodes[u], comp);
        }
    }

    private static void printVer(Vertex[] nodes, int maxComp, int n){
        //nodes[i].visit = 1;
        for(int i = 0; i < n; i++)
            for(int j = 0; j <nodes[i].edge.size(); j++){
                int k = nodes[i].edge.get(j);
                if (i <= k){
                    System.out.printf("%d -- %d ", i, k);
                    if (nodes[i].numComp == maxComp)
                        System.out.print("[color = red]");
                    System.out.print("\n");
                }

            }
    }

    public static void main(String[] args) {
        long start = System.currentTimeMillis();
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        Vertex[] nodes = new Vertex[n];
        int m = in.nextInt();

        for (int i = 0; i < n; i++) {
            nodes[i] = new Vertex();
            nodes[i].visit = 0;
            nodes[i].numComp = -1;
        }
        for(int i = 0; i < m; i++){
            int u, v;
            u = in.nextInt();
            v = in.nextInt();
            nodes[u].edge.add(v);
            if (u != v){
                nodes[v].edge.add(u);
            }
        }



        int maxNodes = -1, maxEdge = -1, comp = 0, maxComp = 0;


        for(Vertex v : nodes){
            if(v.visit == 0){

                countEdge = 0;
                countVer = 0;
                visitVertex(nodes, v, comp);
                countEdge/=2;
                comp++;
            }
            if(countVer > maxNodes){
                maxNodes = countVer;
                maxEdge = countEdge;
                maxComp = comp - 1;
            }
            else
            if(countVer == maxNodes && countEdge > maxEdge){
                maxEdge = countEdge;
                maxComp = comp - 1;
            }
        }


        System.out.println("graph {");
        for(int i = 0; i < n; i++){
            System.out.printf("%d ", i);
            if(nodes[i].numComp == maxComp)
                System.out.print("[color = red]");
            System.out.print("\n");
        }
        //for(int i = 0; i < n; i++)
        //  nodes[i].visit = 0;
        //for(int i = 0; i < n; i++)
        printVer(nodes, maxComp, n);
        System.out.println("}");
        System.out.println((double) (System.currentTimeMillis() - start));
    }
}