#include<stdio.h> // printf()
#include<stdlib.h> // malloc(), free()
#include<limits.h> // INT_MAX for noEdgeValue

typedef int ElemType;

typedef int BOOL;
#define TRUE 0
#define FALSE -1

////////////////////////////////////////////////////////////////////////////////
// P.34
// Program 3.2 Queue
typedef struct
{
    int front;
    int rear;
    int maxSize;
    ElemType* element;
}Queue;

void Create(Queue* Q, int mSize)
{
    Q->maxSize = mSize;
    Q->element = (ElemType*)malloc(sizeof(ElemType) * mSize);
    Q->front = Q->rear = 0;
}

// Function name conflicted with Destroy() of mGraph, so I changed its name...
void Destroy_Queue(Queue* Q)
{
    Q->maxSize = -1;
    free(Q->element);
    Q->front = Q->rear = -1;
}

BOOL IsEmpty(Queue* Q)
{
    return Q->front == Q->rear;
}

BOOL IsFull(Queue* Q)
{
    return (Q->rear + 1) % Q->maxSize == Q->front;
}

BOOL Front(Queue * Q, ElemType * x)
{
    if (IsEmpty(Q))
        return FALSE;

    *x = Q->element[(Q->front + 1) % Q->maxSize];

    return TRUE;
}

BOOL EnQueue(Queue * Q, ElemType x)
{
    if (IsFull(Q))
        return FALSE;

    Q->rear = (Q->rear + 1) % Q->maxSize;
    Q->element[Q->rear] = x;

    return TRUE;
}

BOOL DeQueue(Queue * Q)
{
    if (IsEmpty(Q))
        return FALSE;

    Q->front = (Q->front + 1) % Q->maxSize;

    return TRUE;
}

void Clear(Queue * Q)
{
    Q->front = Q->rear = 0;
}
////////////////////////////////////////////////////////////////////////////////

////////////////////////////////////////////////////////////////////////////////
// MGraph
// P.139 - 141

// P.139
typedef int ElemType;
typedef struct
{
    ElemType** a;
    int n;
    int e;
    ElemType noEdge;
}mGraph;

// P.139 Program 9.1
#define ERROR 0
#define OK 1
#define Overflow 2
#define Underflow 3
#define NotPresent 4
#define Duplicate 5
typedef int Status;

Status Init(mGraph * mg, int nSize, ElemType noEdgeValue)
{
    int i, j;

    mg->n = nSize;
    mg->e = 0;
    mg->noEdge = noEdgeValue;
    mg->a = (ElemType * *)malloc(nSize * sizeof(ElemType*));
    if (!mg->a)
        return ERROR;

    for (i = 0; i < mg->n; i++)
    {
        mg->a[i] = (ElemType*)malloc(nSize * sizeof(ElemType));

        for (j = 0; j < mg->n; j++)
            mg->a[i][j] = mg->noEdge;

        mg->a[i][i] = 0;
    }

    return OK;
}

// P.140 Program 9.2
void Destroy(mGraph * mg)
{
    int i;

    for (i = 0; i < mg->n; i++)
        free(mg->a[i]);

    free(mg->a);
}

// P.140 Program 9.3
Status Exist(mGraph * mg, int u, int v)
{
    if (u<0 || v<0 || u>mg->n - 1 || v>mg->n - 1 || u == v || mg->a[u][v] == mg->noEdge)
        return ERROR;

    return OK;
}

// P.140 Program 9.4
Status Insert(mGraph * mg, int u, int v, ElemType w)
{
    if (u<0 || v<0 || u>mg->n - 1 || v>mg->n - 1 || u == v)
        return ERROR;

    if (mg->a[u][v] != mg->noEdge)
        return Duplicate;

    mg->a[u][v] = w;
    mg->e++;

    return OK;
}

// P.140 Program 9.5
Status Remove(mGraph * mg, int u, int v)
{
    if (u<0 || v<0 || u>mg->n - 1 || v>mg->n - 1 || u == v)
        return ERROR;

    if (mg->a[u][v] == mg->noEdge)
        return NotPresent;

    mg->a[u][v] = mg->noEdge;
    mg->e--;

    return OK;
}
////////////////////////////////////////////////////////////////////////////////

////////////////////////////////////////////////////////////////////////////////
// DFS
// There are not any DFS programs based on MGraph in the textbook, 
// so I made it...
void DFS(int v, int visited[], mGraph g)
{
    int i;

    printf("%d ", v);
    visited[v] = 1;

    for (i = 0; i < g.n; i++)
    {
        if (g.a[v][i] != 0 && g.a[v][i] != g.noEdge && !visited[i])
        {
            DFS(i, visited, g);
        }
    }
}

void DFSGraph(mGraph g)
{
    int i;

    // Init visited
    int* visited = malloc(g.n * sizeof(int));
    for (i = 0; i < g.n; i++)
        visited[i] = 0;

    // Do DFS
    for (i = 0; i < g.n; i++)
    {
        if (!visited[i])
        {
            DFS(i, visited, g);
        }
    }

    free(visited);
}
////////////////////////////////////////////////////////////////////////////////

////////////////////////////////////////////////////////////////////////////////
// BFS
// There are not any BFS programs based on MGraph in the textbook, 
// so I made it...
void BFS(int v, int visited[], mGraph g)
{
    int i;

    Queue q;
    Create(&q, g.n);

    visited[v] = 1;
    printf("%d ", v);

    EnQueue(&q, v);
    while (!IsEmpty(&q))
    {
        Front(&q, &v);
        DeQueue(&q);

        for (i = 0; i < g.n; i++)
        {
            if (g.a[v][i] != 0 && g.a[v][i] != g.noEdge && !visited[i])
            {
                visited[i] = 1;
                printf("%d ", i);
                EnQueue(&q, i);
            }

        }
    }
}

void BFSGraph(mGraph g)
{
    int i;

    // Init visited
    int* visited = malloc(g.n * sizeof(int));
    for (i = 0; i < g.n; i++)
        visited[i] = 0;

    // Do BFS
    for (i = 0; i < g.n; i++)
    {
        if (!visited[i])
        {
            BFS(i, visited, g);
        }
    }

    free(visited);
}
////////////////////////////////////////////////////////////////////////////////

////////////////////////////////////////////////////////////////////////////////
int main()
{
    mGraph GBA;
    int nSize = 0, edge = 0;
    int u = 0, v = 0;
    scanf("%d %d", &nSize, &edge);
    Init(&GBA, nSize, 0);
    for (int a = 0; a < edge; a++)
    {
        scanf("%d %d", &u, &v);
        Insert(&GBA, u, v, 1);
        Insert(&GBA, v, u, 1);
    }
    for (int f = 0; f < nSize; f++)
    {
        for (int r = 0; r < nSize; r++)
            printf("%d ", GBA.a[f][r]);
        printf("\n");
    }
    BFSGraph(GBA);

    Destroy(&GBA);

    return 0;
}