#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 1;
vector<int> adj[maxn];
int deg[maxn], pos[maxn];
int main() {
int n; cin >> n;
int a, b;
for (int i = 0; i < n - 1; i++) {
cin >> a >> b;
--a, --b;
adj[a].push_back(b);
adj[b].push_back(a);
++deg[a], ++deg[b];
pos[i] = i;
}
pos[n - 1] = n - 1;
unordered_set<int> leafs;
for (int i = 0; i < n; i++) if (deg[i] == 1) leafs.insert(i);
int sol = 0;
while (!leafs.empty()) {
int cur = *leafs.begin();
leafs.erase(leafs.begin());
int next = adj[cur][0];
if (pos[cur] == cur) {
sol += 2;
swap(pos[cur], pos[next]);
}
if (--deg[next] == 1) leafs.insert(adj[cur][0]);
adj[next].erase(find(adj[next].begin(), adj[next].end(), cur));
}
cout << sol << ' ' << 1 << '\n';
vector<int> loc(n);
for (int i = 0; i < n; i++) {
loc[pos[i]] = i;
assert(pos[i] != i);
}
for (int i = 0; i < n; i++) cout << loc[i] + 1 << ' ';
cout << '\n';
for (int i = 0; i < n; i++) cout << 1 << ' ';
cout << '\n';
}
