#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
void DFS(int);
vector<int>Grafo[1005];
int Visitados[1005];
int CConexas;
int main() {
    int V,E,x,y;
    scanf("%d %d",&V, &E);
    while(E--) {
        scanf("%d %d",&x, &y);
        Grafo[x].push_back(y);
        Grafo[y].push_back(x);
    }
    for(int j = 1 ; j <= V ; j ++) {
        printf("%d : ",j);
        for(int  k = 0 ; k < Grafo[j].size() ; k++){
            printf("%d ",Grafo[j][k]);
        }
        printf("\n");
    }
    CConexas = 1;
    memset(Visitados,0,sizeof(Visitados));
    for(int i = 1 ; i <= V; i++) {
        if(Visitados[i] == 0) {
            DFS(i);
            CConexas++;
        }
    }
    for(int a=1;a<=V;a++) printf("%d ",Visitados[a]);
    printf("\nComponentes Conexas: %d\n",CConexas-1);
    return 0;
}
void DFS(int u) {
    Visitados[u] = CConexas;
    for(int l = 0 ; l < Grafo[u].size(); l++) {
        int v = Grafo[u][l];
        if(Visitados[v] == 0) DFS(v);
    }
}