#include <stdio.h>
#include <stdlib.h>

#define ERROR -1

typedef int ElemType;
typedef int Position;
typedef struct QNode* Queue;

typedef struct QNode{
    ElemType*data;
    Position front;
    Position rear;
    int maxSize;
};

Queue CreateQueue(int maxSize){
    Queue Q = (Queue)malloc(sizeof(struct QNode));
    Q->data = (ElemType*)malloc(sizeof(ElemType)*(maxSize + 1));
    Q->front = 0;
    Q->rear = 0;
    Q->maxSize = maxSize + 1;
    return Q;
}

void DestroyQueue(Queue Q) {
    if (Q) {
        if(Q->data){
            free(Q->data);
        }
        free(Q);
    }
}

int IsFullQueue(Queue Q){
    return (Q->front == (Q->rear + 1) % Q->maxSize);
}

void Enqueue(Queue Q, ElemType item) {
    if (IsFullQueue(Q)) {
        return;
    }
    Q->rear = (Q->rear + 1) % Q->maxSize;
    Q->data[Q->rear] = item;
} 

int IsEmptyQueue(Queue Q){
    return ( Q->front == Q->rear );
}

ElemType Dequeue(Queue Q){
    if (IsEmptyQueue(Q)){
        return ERROR;
    }
    Q->front = (Q->front + 1) % Q->maxSize;
    return Q->data[Q->front];
}

int m[10][10];

void Print(int i){
    printf(" %d", i);
    //如果访问过点i，则标记点ii为-1
    m[i][i] = -1;
}

void DFS_Traversal(int N, int i){
    if(m[i][i] != 0){
        return;
    }
    Print(i);
    for(int j = 0; j < N; ++j){
        if(i != j && m[i][j] == 1){
            DFS_Traversal(N, j);
        }
    }
}

void DFS(int N){
    for(int i = 0; i < N; ++i){
        if(m[i][i] == 0)
        {
            printf("{");
            DFS_Traversal(N, i);
            printf(" }\n");
        }
    }
}

void BFS_Traversal(int N, int i, Queue Q){
    if(m[i][i] != 0){
        return;
    }
    Print(i);
    for(int j = 0; j < N; ++j){
        if(i != j && m[j][j] == 0 && m[i][j] == 1){
            Enqueue(Q, j);
        }
    }
}

void BFS(int N){
    for(int i = 0; i < N; ++i){
        if(m[i][i] == 0){
            printf("{");
            Queue Q = CreateQueue(N);
            Enqueue(Q, i);
            while(!IsEmptyQueue(Q))
            {
                int j = Dequeue(Q);
                BFS_Traversal(N, j, Q);
            }
            printf(" }\n");
        }
       
    }
}

int main(){
    //memset(m, 0, 100*sizeof(int));
    int N,E;
    scanf("%d %d", &N, &E);
    int v1,v2;
    for(int i = 0; i < E; ++i){
        scanf("%d %d", &v1, &v2);
        m[v1][v2] = 1;
        m[v2][v1] = 1;
    }
    DFS(N);
    for(int j = 0; j < N; ++j){
        m[j][j] = 0;
    }
    BFS(N);
    return 0;
}