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


#include <vector>
#define pb push_back
#define LE 100666

ifstream f("treespotting.in");

vector<int> H[LE];
bool viz[LE],MARK[LE];
int lev[LE],fth[LE];

void dfs(int nod)
{
    viz[nod]=true;
    int N=H[nod].size(),i;

    for(i=0; i<N; ++i)
    {
        int D=H[nod][i];
        if (viz[D]==false)
        {
            fth[D]=nod;
            lev[D]=lev[nod]+1;
            dfs(D);
        }
    }
}

void lca(int nod1,int nod2)
{
    int n1=nod1,n2=nod2,last_mark=0;

    while (n1!=n2)
    {
        if (lev[n1]>lev[n2]) n1=fth[n1];
        else n2=fth[n2];

        if (n1!=nod1&&n1!=nod2) last_mark=n1;
        if (n2!=nod2&&n2!=nod1) last_mark=n2;
    }

    if (nod1!=n1)
        for(nod1=fth[nod1];  ; )
        {
            MARK[nod1]=true;
            if (nod1==last_mark) break;
            nod1=fth[nod1];
            fth[nod1]=last_mark;
        }

    if (nod2!=n1)
        for(nod2=fth[nod2];  ; )
        {
            MARK[nod2]=true;
            if (nod2==last_mark) break;
            nod2=fth[nod2];
            fth[nod2]=last_mark;
        }
}

int main()
{
    int n,m,i;
    f>>n>>m;
    for(i=1; i<n; ++i)
    {
        int xx,yy;
        f>>xx>>yy;
        H[xx].pb(yy);
        H[yy].pb(xx);
    }

    dfs(1);

    /*   for(i=1;i<=n;++i)
         cout<<lev[i]<<" ";
       cout<<'\n'<<'\n';

       for(i=1;i<=n;++i)
         cout<<fth[i]<<" ";
    */

    for(i=1; i<=m-n+1; ++i)
    {
        int xx,yy;
        f>>xx>>yy;
        H[xx].pb(yy);
        lca(xx,yy);
    }

    for(i=1; i<=n; ++i)
        cout<<MARK[i]<<" ";

    cout<<'\n'<<'\n';

    for(i=1; i<=n; ++i)
        cout<<fth[i]<<" ";


    return 0;
}