#include<bits/stdc++.h>
using namespace std;
vector<int>v[200001];
int arr[1024][1024];
bool used[200001];
int n,p,x,y,B;
ifstream fin("puzzle.in");
ofstream fout("puzzle.out");
void print()
{
    int i,j;
    for(j=0;j<x;j++)
    {
        for(i=0;i<y;i++)
        {
            fout<<arr[i][j]<<" ";
        }fout<<endl;
    }
}
void solve2(int st)
{
    memset(used,0,sizeof(used));
    memset(arr,0,sizeof(arr));
    arr[0][0]=B;
    int i,j,l;
    int prev=st;
    for(i=0;i<y;i++)
    {
        if(!i)j=1;
        else j=0;
        for(j;j<x;j++)
        {
            //cout<<i<<" "<<j<<endl;
            if(i!=0&&i!=y-1)
            {prev=arr[i-1][j];
                if(j!=0&&j!=x-1)
                {
                    for(l=0;l<v[prev].size();l++)
                    {
                        int nb=v[prev][l];
                        if(!used[nb]&&v[nb].size()==4)
                        {
                            arr[i][j]=nb;
                            used[nb]=1;break;
                        }
                    }
                }
                else
                {
                    for(l=0;l<v[prev].size();l++)
                    {
                        int nb=v[prev][l];
                        if(!used[nb]&&v[nb].size()==3)
                        {
                            arr[i][j]=nb;
                            used[nb]=1;break;
                        }
                    }
                }
            }
            else
            {if(i==y-1)prev=arr[i-1][j];
                else prev=arr[i][j-1];
                if(j!=0&&j!=x-1)
                {
                    for(l=0;l<v[prev].size();l++)
                    {
                        int nb=v[prev][l];
                        if(!used[nb]&&v[nb].size()==3)
                        {
                            arr[i][j]=nb;
                            used[nb]=1;break;
                        }
                    }
                }
                else
                {
                    //cout<<i<<" - > "<<j<<endl;
                    for(l=0;l<v[prev].size();l++)
                    {
                        int nb=v[prev][l];
                        //cout<<nb<<endl;
                        if(!used[nb]&&v[nb].size()==2)
                        {
                            //cout<<prev<<" "<<nb<<endl;
                            arr[i][j]=nb;
                            used[nb]=1;break;
                        }
                    }
                }

            }
        }
    }
    print();
}
void solve(int st)
{
    int i,j,l;
    int prev=st;
    for(i=0;i<y;i++)
    {
        if(!i)j=1;
        else j=0;
        for(j;j<x;j++)
        {
            //cout<<i<<" "<<j<<endl;
            if(i!=0&&i!=y-1)
            {prev=arr[i-1][j];
                if(j!=0&&j!=x-1)
                {
                    for(l=v[prev].size()-1;l>=0;l--)
                    {
                        int nb=v[prev][l];
                        if(!used[nb]&&v[nb].size()==4)
                        {
                            arr[i][j]=nb;
                            used[nb]=1;break;
                        }
                    }
                }
                else
                {
                    for(l=v[prev].size()-1;l>=0;l--)
                    {
                        int nb=v[prev][l];
                        if(!used[nb]&&v[nb].size()==3)
                        {
                            arr[i][j]=nb;
                            used[nb]=1;break;
                        }
                    }
                }
            }
            else
            {if(i==y-1)prev=arr[i-1][j];
                else prev=arr[i][j-1];
                if(j!=0&&j!=x-1)
                {
                    for(l=v[prev].size()-1;l>=0;l--)
                    {
                        int nb=v[prev][l];
                        if(!used[nb]&&v[nb].size()==3)
                        {
                            arr[i][j]=nb;
                            used[nb]=1;break;
                        }
                    }
                }
                else
                {
                    //cout<<i<<" - > "<<j<<endl;
                    for(l=v[prev].size()-1;l>=0;l--)
                    {
                        int nb=v[prev][l];
                        //cout<<nb<<endl;
                        if(!used[nb]&&v[nb].size()==2)
                        {
                            //cout<<prev<<" "<<nb<<endl;
                            arr[i][j]=nb;
                            used[nb]=1;break;
                        }
                    }
                }

            }
        }
    }
    int nb=arr[y-1][x-1];
    int lamp=0;
    for(i=0;i<v[nb].size();i++)
    {
        if(v[nb][i]==arr[y-2][x-1])lamp++;
        if(v[nb][i]==arr[y-1][x-2])lamp++;
    }
    if(lamp==2)print();
    else solve2(st);
}
int main()
{
    int i,j,l;
    fin>>n>>p;
    for(i=0; i<p; i++)
    {
        fin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    for(i=sqrt(n); i>=2; i--)
    {
        if(n%i==0)
        {
            j=n/i;
            if(2*i*j-i-j==p)
            {
                x=i;
                y=j;
                break;
            }
        }
    }
    int st;
    for(i=1;i<=n;i++)
    {
        if(v[i].size()==2)
        {
            arr[0][0]=i;
            used[i]=true;
            st=i;
            B=i;
            break;
        }
    }
    fout<<x<<" "<<y<<endl;
    solve(st);
    return 0;
}
/*
l=0;l<v[prev].size();l++
*/
/*
l=v[prev].size()-1;l>=0;l--;
*/