#include <bits/stdc++.h>
using namespace std;
int main() {
int n; cin >> n;
vector<vector<int>> graph(n);
for (int i = 0; i < n-1; i++) {
int x,y; cin >> x >> y;
graph[x-1].push_back(y-1);
graph[y-1].push_back(x-1);
}
//BFS with delimiter for depth tracking
//we always root at 0
bool vis[n] = {};
int depth[n] = {};
queue<int> bfs;
stack<int> rev_bfs;
bfs.push(0);
bfs.push(-1);
vis[0] = true;
int curr_depth = 0;
while(!bfs.empty()) {
int x = bfs.front();
bfs.pop();
rev_bfs.push(x);
if (x == -1) {
if (!bfs.empty()) {
bfs.push(-1);
}
curr_depth++;
} else {
for (int i = 0; i < graph[x].size(); i++) {
if (vis[graph[x][i]] == false) {
vis[graph[x][i]] = true;
bfs.push(graph[x][i]);
}
}
depth[x] = curr_depth;
}
}
for (int i = 0; i < n; i++) {
vis[i] = false;
}
int arr[n] = {};
for (int i = 0; i < n; i++) {
arr[i] = i;
}
int min = 0;
while (!rev_bfs.empty()) {
int x = rev_bfs.top();
rev_bfs.pop();
if (vis[x] == false) {
int parent = 0;
for (int i = 0; i < graph[x].size(); i++) {
if (depth[graph[x][i]] < depth[x]) {
parent = graph[x][i];
}
}
vector<int> shift;
shift.push_back(parent);
vis[parent] = true;
for (int i = 0; i < graph[parent].size(); i++) {
if (depth[graph[parent][i]] > depth[parent] and vis[graph[parent][i]] == false) {
shift.push_back(graph[parent][i]);
vis[graph[parent][i]] = true;
}
}
for (int i = 0; i < shift.size(); i++) {
arr[shift[i]] = shift[(i+1) % shift.size()];
}
min += 2*(shift.size()-1);
if (shift.size() == 1) {
vis[parent] = false;
}
}
}
//edge case checker
if (arr[0] == 0) {
arr[0] = arr[graph[0][0]];
arr[graph[0][0]] = 0;
min += 2;
}
cout << min << " " << min << '\n';
for (int i = 0; i < n; i++) {
cout << arr[i]+1 << " ";
}
cout << '\n';
for (int i = 0; i < n; i++) {
cout << arr[i]+1 << " ";
}
cout << '\n';
return 0;
}
