#include <fstream>
#include <vector>
using namespace std;

ifstream is("a.in");
ofstream os("a.out");

vector < vector<int> > G;
vector<int> E, D, P, Intervale;
int n, m;

void Read();
void Euler(int x, int d = 1);
void Actualizare(int nod, int st, int dr);

int main()
{
    Read();
    Euler(1);
    Intervale.resize(4*n+1);

    for ( auto it : E )
        os << it;
    os << "\n";
    for ( auto it : E )
        os << D[it];
    os << "\n";
    for ( auto it : E )
        os << P[it];

    is.close();
    os.close();
    return 0;
}
void Read()
{
    is >> n >> m;
    G.resize(n+1);
    D.resize(n+1);
    P.resize(n+1);
    for ( int i = 0, x, y; i < m; ++i )
    {
        is >> x >> y;
        G[x].push_back(y);
    }
}
void Euler(int x, int d)
{
    E.push_back(x);
    D[x] = d;
    P[x] = E.size() - 1;
    for ( auto it: G[x] )
    {
        Euler(it, d+1);
        E.push_back(x);
    }
}
void Actualizare(int nod, int st, int dr, int poz, int val)
{
    if ( st == dr )
    {
        Intervale[nod] = val;
        return;
    }
    int m = (st+dr)/2;
    if ( m <= poz )
        Actualizare(2*nod, st, m, poz, val);
    else
        Actualizare(2*nod+1, m+1, dr, poz, val);
    Intervale[nod] = D[Intervale[2*nod]] < D[Intervale[2*nod+1]] ? Intervale[2*nod] : Intervale[2*nod+1];
}