#include <iostream>
#include <random>
#include <algorithm>
#include "tree2.h"
using namespace std;

static mt19937 mt(1111111);

static int num[100000];

int main() {
    int n; cin >> n;
    for(int i = 1; i <= n; i++) num[i]=i;
    vector<pair<int,int>> v, ans2;
    for(int i = 0; i < n-1; i++) {
        int a,b; cin >> a >> b;
        v.push_back({a, b});
    }
    bool b=0;
    vector<int> ans = encode(n, v);
    cout << "Removed nodes: ";
    for(auto &x : ans) {cout << x << " "; b|=(x==1);}
    cout << endl;

    int ptr=-1;
    if(b) {
        num[1]=-1;
        ptr--;
        ans.erase(remove(ans.begin(), ans.end(), 1), ans.end());
    }
    shuffle(ans.begin(), ans.end(), mt);
    for(auto &x : ans) {
        num[x]=ptr;
        ptr--;
    }
    cout << "New node numbers: ";
    for(int i = 1; i <= n; i++) {
        cout << num[i] << " ";
    }
    cout << endl;
    
    cout << "Decoded: " << endl;
    for(int i = 0; i < v.size(); i++) {
        v[i].first=num[v[i].first];
        v[i].second=num[v[i].second];
        if(mt()%2) swap(v[i].first, v[i].second);
    }
    ans2=decode(n, v);
    for(auto &x : ans2) {
        cout << x.first << ' ' << x.second << endl;
    }
}