#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
auto&operator<<(auto &o, pair<auto, auto> p) {o << "(" << p.first << ", " << p.second << ")"; return o;}
auto operator<<(auto&o,auto x)->decltype(x.end(),o){o<<"{"; for(auto e : x) o<<e<<", "; return o<<"}";}
#define debug(X) cerr << "["#X"]: " << X << '\n';
#else
#define cerr if(0)cout
#define debug(X) ;
#endif
using ll = long long;
#define all(v) (v).begin(), (v).end()
#define ssize(x) int(x.size())
#define fi first
#define se second
#define mp make_pair
#define eb emplace_back
void dfs(int v, int p, vector<int> &match, const vector<vector<int>> &g) {
for (int u : g[v]) {
if (u == p) continue;
dfs(u, v, match, g);
}
if (match[v] != -1) return;
for (int u : g[v]) {
if (match[u] == -1) {
match[v] = u;
match[u] = v;
}
}
}
vector<int> matching(const vector<vector<int>> &g) {
int n = ssize(g);
vector<int> match(n, -1);
dfs(0, -1, match, g);
return match;
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(nullptr);
int n;
cin >> n;
vector<vector<int>> g(n);
for (int i = 0; i < n-1; ++i) {
int u, v;
cin >> u >> v;
g[u-1].eb(v-1);
g[v-1].eb(u-1);
}
vector<int> match = matching(g);
int mn = n;
for (int v = 0; v < n; ++v) {
if (match[v] != -1) continue;
mn++;
int u = g[v][0];
match[v] = match[u];
match[u] = v;
}
cout << mn << ' ' << mn << '\n';
for (int x : match) cout << x+1 << ' ';
cout << '\n';
for (int x : match) cout << x+1 << ' ';
cout << '\n';
return 0;
}
