#include <iostream>
#include <fstream>
#include <stack>
#include <vector>
#define MAX 100005

using namespace std;

ifstream f("biconex.in");
ofstream g("biconex.out");

stack <int> stk;

vector <int> v[MAX] , sol[MAX];

int viz[MAX] , niv[MAX] , nivmin[MAX] , comp , n , m , x , y;

void dfs (int nod , int lvl)
{
    viz[nod] = 1;
    niv[nod] = nivmin[nod] = lvl;
    stk.push (nod);
    for (auto vecin : v[nod])
    {
        if (viz[vecin] == 1)
            nivmin[nod] = min(nivmin[nod] , niv[vecin]);
        else
        {
            dfs (vecin , lvl + 1);

            if (niv[nod] <= nivmin[vecin])
            {
                comp++;
                while (stk.top () != vecin)
                {
                    sol[comp].push_back (stk.top ());
                    stk.pop ();
                }
                sol[comp].push_back (stk.top ());
                sol[comp].push_back (nod);
                stk.pop();
            }
            nivmin[nod] = min (nivmin[nod] , nivmin[vecin]);
        }
    }
}

int main()
{
    f >> n >> m;
    for (int i = 1 ; i <= m ; i++)
    {
        f >> x >> y;
        v[x].push_back (y);
        v[y].push_back (x);
    }

    dfs (1 , 1);
    for (int i = 1 ; i <= n ; i++)
        g << nivmin[i] <<" ";
    g << '\n';
    for (int i = 1 ; i <= n ; i++)
        g << niv[i] <<" ";
/*
    g << comp << '\n';

    for (int i = 1 ; i <= comp ; i++)
    {
        for (auto j : sol[i])
            g << j << " ";
        g << '\n';
    }
    */
    return 0;
}