#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#include <set>
#include <queue>
#include <stack>
#define ll long long
#define lf double
#define _1 first
#define _2 second
#define _mp make_pair
#define _pb push_back
#define MAX_N 222222
#define inf 2222222222222222222ll

using namespace std;

ll read(){ll x = 0;char c = 0, v = 0;do{c = getchar();if(c == '-')v = 1;} while(c < '0' || c > '9');do{x = (x << 3) + (x << 1) + c - '0';c = getchar();} while(c >= '0' && c <= '9');return v ? -x : x;}

template<size_t N>
struct Tree
{
    int n, rt;
    vector<int> G[N];
    void build(int x, int y)
    {
        G[x]._pb(y);
        G[y]._pb(x);
        n = max(n, max(x, y));
    }

    #define Edgs(p, x, f) for(auto p: G[x]) if(p != (f))
    int SIZE, MNVAL, MNPOS;
    void Gdfs1(int x, int f)
    {
        SIZE++;
        Edgs(p, x, f)
            Gdfs1(p, x);
    }

    int Gdfs2(int x, int f)
    {
        int sz = 1, mxsz = 0;
        Edgs(p, x, f)
        {
            int d = Gdfs2(p, x);
            sz += d;
            mxsz = max(mxsz, d);
        }
        mxsz = max(mxsz, SIZE - sz);
        if(mxsz < MNVAL)
            MNVAL = mxsz, MNPOS = x;
        return sz;
    }

    int Gx()
    {
        SIZE = 0, MNVAL = N, MNPOS = 0;
        Gdfs1(1, 0), Gdfs2(1, 0);
        return MNPOS;
    }

    int sz[N];
    void dfs1(int x, int f)
    {
        sz[x] = 1;
        Edgs(p, x, f)
        {
            dfs1(p, x);
            sz[x] += sz[p];
        }
    }

    ll dp[N][2];
    int mat1[N];
    ll ans1;
    void dfs2(int x, int f)
    {
        if(sz[x] == 1)
        {
            dp[x][0] = -2 * (int)N;
            dp[x][1] = 0;
            return;
        }
        dp[x][0] = 1, dp[x][1] = 0;
        bool flag = 0;
        Edgs(p, x, f)
        {
            dfs2(p, x);
            dp[x][1] += dp[p][0];
            if(dp[p][0] > dp[p][1])
                dp[x][0] += dp[p][0];
            else
                flag = 1, dp[x][0] += dp[p][1];
        }
        if(flag)
            return;
        ll mn = N;
        Edgs(p, x, f)
            mn = min(mn, dp[p][0] - dp[p][1]);
        dp[x][0] -= mn;
    }

    void output1(int x, int f, bool sta)
    {
        //printf(" %d %d\n", x, (int)sta);
        if(sz[x] == 1)
            return;
        if(sta)
        {
            Edgs(p, x, f)
                output1(p, x, 0);
            return;
        }
        bool flag = 0;
        Edgs(p, x, f)
            if(dp[p][0] <= dp[p][1])
                flag = 1;
        if(flag)
        {
            ll lst = x;
            Edgs(p, x, f)
            {
                if(dp[p][0] > dp[p][1])
                    output1(p, x, 0);
                else
                {
                    mat1[lst] = p;
                    lst = p;
                    output1(p, x, 1);
                }
            }
            mat1[lst] = x;
            return;
        }
        ll mn = N;
        int mnp = 0;
        Edgs(p, x, f)
            if(dp[p][0] - dp[p][1] < mn)
                mn = dp[p][0] - dp[p][1], mnp = p;
        mat1[x] = mnp, mat1[mnp] = x;
        Edgs(p, x, f)
        {
            if(p == mnp)
                output1(p, x, 1);
            else
                output1(p, x, 0);
        }
    }

    int m;
    stack<int> nds[N];
    priority_queue<pair<int, int> > q; // <size, id>
    int mat2[N];
    ll ans2;
    void dfs3(int x, int f, int d, int id)
    {
        nds[id].push(x);
        ans2 += 2 * d;
        Edgs(p, x, f)
            dfs3(p, x, d + 1, id);
    }

    void main()
    {
        rt = Gx();
        //printf("%d\n", rt);
        dfs1(rt, 0);
        dfs2(rt, 0);
        ans1 = 2 * (n - dp[rt][0]);
        output1(rt, 0, 0);
        return;
        m = ans2 = 0;
        Edgs(p, rt, 0)
        {
            m++;
            dfs3(p, rt, 1, m);
            q.push(_mp(sz[p], p));
        }
        for(int i = 1; 2 * i < n; i++)
        {
            pair<int, int> p1 = q.top();
            q.pop();
            pair<int, int> p2 = q.top();
            q.pop();
            int x1 = nds[p1._2].top();
            nds[p1._2].pop();
            int x2 = nds[p2._2].top();
            nds[p2._2].pop();
            if(i == 1 && (n & 1))
                mat2[x1] = rt, mat2[rt] = x2, mat2[x2] = x1;
            else
                mat2[x1] = x2, mat2[x2] = x1;
            if(p1._1 > 1)
                q.push(_mp(p1._1 - 1, p1._2));
            if(p2._1 > 1)
                q.push(_mp(p2._1 - 1, p2._2));
        }
        if(!(n & 1))
        {
            pair<int, int> p1 = q.top();
            q.pop();
            int x1 = nds[p1._2].top();
            nds[p1._2].pop();
            mat2[x1] = rt;
            mat2[rt] = x1;
        }
    }
};

Tree<MAX_N> tr;
int n;

void MAIN()
{
    n = read();
    for(int i = 1; i < n; i++)
        tr.build(read(), read());
    tr.main();
    printf("%lld %lld\n", tr.ans1, tr.ans2);
    for(int i = 1; i <= n; i++)
        printf("%d ", tr.mat1[i]);
    printf("\n");
    for(int i = 1; i <= n; i++)
        printf("%d ", tr.mat2[i]);
    printf("\n");
}

void CLEAR()
{
    ;
}

void EXP()
{
    ;
}

int main()
{
    EXP();
    int T = 1;
    while(T--)
        MAIN(), CLEAR();
    return 0;
}