#include <bits/stdc++.h>
using namespace std;
#define int long long
int ans = 0;
vector<int> gp(200005, 0);
vector<int> cp;
void dfs(vector<int> ap[], int cur, int par) {
for (auto& p : ap[cur]) {
if (p == par) continue;
dfs(ap, p, cur);
if (!gp[p] && !gp[cur]) ans += 2, gp[cur] = 1, gp[p] = 1, swap(cp[cur], cp[p]);
}
}
void dfs2(vector<int> ap[], int cur, int par) {
for (auto& p : ap[cur]) {
if (p == par) continue;
dfs2(ap, p, cur);
if (!gp[p] || !gp[cur]) ans += 2, gp[cur] = 1, gp[p] = 1, swap(cp[cur], cp[p]);
}
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
vector<int> ap[n + 1];
for (int i = 0; i < n - 1; i++) {
int u, v;
cin >> u >> v;
ap[u].push_back(v);
ap[v].push_back(u);
}
for (int i = 0; i <= n; i++) {
cp.push_back(i);
}
dfs(ap, 1, -1);
dfs2(ap, 1, -1);
cout << ans << ' ' << 1 << '\n';
for (int i = 1; i <= n; i++) cout << cp[i] << ' ';
for (int i = 1; i <= n; i++) cout << 1 << ' ';
return 0;
}
/*
*/
