#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <vector>
using namespace std;

/**
Assumed constraints:
N,M <= 500
K <= 500 000 (implied by previous constraint)
There is always a solution
**/

int grid[511][511];
int n,m;
int k,p;
bool isCorner[500111];
vector<int> Graph[500111];
int Path[500111];
int L=0;

bool used[500111];

int q[500111];
int qL=0;
bool TFO[500111];
int comefrom[500111];

void BFS(int ver)
{
    int i;
    int uk=1;
    int cver,nver;

    qL=1;
    q[qL]=ver;
    TFO[ver]=true;

    while(uk<=qL)
    {
        cver=q[uk];

        if (cver!=ver && isCorner[cver])
        {
            break;
        }

        for (i=0;i<Graph[cver].size();i++)
        {
            nver=Graph[cver][i];

            if (!TFO[nver])
            {
                TFO[nver]=true;
                qL++;
                q[qL]=nver;
                comefrom[qL]=uk;
            }
        }

        uk++;
    }

    L=1;
    Path[L]=q[uk];

    while(uk!=1)
    {
        uk=comefrom[uk];
        L++;
        Path[L]=q[uk];
    }

    reverse(Path+1,Path+1+L);

    return;
}

int getUnused(int ver)
{
    int i;

    for (i=0;i<Graph[ver].size();i++)
    {
        if (!used[ Graph[ver][i] ])
            return Graph[ver][i];
    }

    return -1;
}

int main()
{
    freopen("puzzle.in","r",stdin);
    freopen("puzzle.out","w",stdout);

    int i,j;
    int myCorner;
    int a,b;

    scanf("%d %d",&k,&p);

    for (i=1;i<=p;i++)
    {
        scanf("%d %d",&a,&b);

        Graph[a].push_back(b);
        Graph[b].push_back(a);
    }

    for (i=1;i<=k;i++)
    {
        if (Graph[i].size()==2)
        {
            isCorner[i]=true;
            myCorner=i;
        }
    }

    BFS(myCorner);

    m=L;
    n=k/m;

    printf("%d %d\n",n,m);

    for (i=1;i<=m;i++)
    {
        grid[1][i]=Path[i];
        used[ Path[i] ]=true;
    }

    for (i=2;i<=n;i++)
    {
        for (j=1;j<=m;j++)
        {
            grid[i][j]=getUnused(grid[i-1][j]);

            used[ grid[i][j] ]=true;
        }
    }

    for (i=1;i<=n;i++)
    {
        for (j=1;j<=m;j++)
        {
            printf("%d",grid[i][j]);

            if (j!=m)
                printf(" ");
        }
        printf("\n");
    }

    return 0;
}