#include <bits/stdc++.h>
using namespace std;
#define name "TENBAI"
#define fi first
#define se second
#define endl '\n'
#define setmin(x, y) x = min((x), (y))
#define setmax(x, y) x = max((x), (y))
#define sqr(x) ((x) * (x))
#define all(x) x.begin(), x.end()
mt19937 hdp(chrono::high_resolution_clock::now().time_since_epoch().count());
int rand(int l, int r){return l + ((hdp() % (r - l + 1)) + r - l + 1) % (r - l + 1);}
const int NM = 1e5 + 5;
const int LG = 20;
pair<int, int> st[NM][LG];
int n, dep[NM], tin[NM], timer;
vector<int> g[NM];
void dfs(int u)
{
st[++timer][0] = {dep[u], u};
tin[u] = timer;
for (int v : g[u])
{
g[v].erase(find(all(g[v]), u));
dep[v] = dep[u] + 1;
dfs(v);
st[++timer][0] = {dep[u], u};
}
}
int lca(int u, int v)
{
u = tin[u], v = tin[v];
if (u > v)
swap(u, v);
int lg = __lg(v - u + 1);
return min(st[u][lg], st[v - (1 << lg) + 1][lg]).se;
}
int dist(int u, int v)
{
return dep[u] + dep[v] - 2 * dep[lca(u, v)];
}
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
#include <bits/extc++.h> /// include-line, keep-include
const ll INF = numeric_limits<ll>::max() / 4;
struct MCMF {
struct edge {
int from, to, rev;
ll cap, cost, flow;
};
int N;
vector<vector<edge>> ed;
vi seen;
vector<ll> dist, pi;
vector<edge*> par;
MCMF(int N) : N(N), ed(N), seen(N), dist(N), pi(N), par(N) {}
void addEdge(int from, int to, ll cap, ll cost) {
if (from == to) return;
ed[from].push_back(edge{ from,to,sz(ed[to]),cap,cost,0 });
ed[to].push_back(edge{ to,from,sz(ed[from])-1,0,-cost,0 });
}
void path(int s) {
fill(all(seen), 0);
fill(all(dist), INF);
dist[s] = 0; ll di;
__gnu_pbds::priority_queue<pair<ll, int>> q;
vector<decltype(q)::point_iterator> its(N);
q.push({ 0, s });
while (!q.empty()) {
s = q.top().second; q.pop();
seen[s] = 1; di = dist[s] + pi[s];
for (edge& e : ed[s]) if (!seen[e.to]) {
ll val = di - pi[e.to] + e.cost;
if (e.cap - e.flow > 0 && val < dist[e.to]) {
dist[e.to] = val;
par[e.to] = &e;
if (its[e.to] == q.end())
its[e.to] = q.push({ -dist[e.to], e.to });
else
q.modify(its[e.to], { -dist[e.to], e.to });
}
}
}
rep(i,0,N) pi[i] = min(pi[i] + dist[i], INF);
}
pair<ll, ll> maxflow(int s, int t) {
ll totflow = 0, totcost = 0;
while (path(s), seen[t]) {
ll fl = INF;
for (edge* x = par[t]; x; x = par[x->from])
fl = min(fl, x->cap - x->flow);
totflow += fl;
for (edge* x = par[t]; x; x = par[x->from]) {
x->flow += fl;
ed[x->to][x->rev].flow -= fl;
}
}
rep(i,0,N) for(edge& e : ed[i]) totcost += e.cost * e.flow;
return {totflow, totcost/2};
}
// If some costs can be negative, call this before maxflow:
void setpi(int s) { // (otherwise, leave this out)
fill(all(pi), INF); pi[s] = 0;
int it = N, ch = 1; ll v;
while (ch-- && it--)
rep(i,0,N) if (pi[i] != INF)
for (edge& e : ed[i]) if (e.cap)
if ((v = pi[i] + e.cost) < pi[e.to])
pi[e.to] = v, ch = 1;
assert(it >= 0); // negative cost cycle
}
};
int ans1[NM], ans2[NM];
void solve()
{
cin >> n;
for (int i = 1; i < n; i++)
{
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
dfs(1);
for (int i = 1; (1 << i) <= timer; i++)
for (int j = 1; j + (1 << i) - 1 <= timer; j++)
st[j][i] = min(st[j][i - 1], st[j + (1 << i - 1)][i - 1]);
MCMF mcmf(2 * n + 2);
for (int i = 1; i <= n; i++)
{
mcmf.addEdge(0, i, 1, 0);
mcmf.addEdge(n + i, 2 * n + 1, 1, 0);
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (i != j)
mcmf.addEdge(i, n + j, 1, dist(i, j));
cout << mcmf.maxflow(0, 2 * n + 1).se << ' ' << 0 << endl;
for (auto x : mcmf.ed)
for (auto y : x)
if (y.flow && y.from >= 1 && y.from <= n)
ans1[y.from] = y.to - n;
for (int i = 1; i <= n; i++)
cout << ans1[i] << " \n"[i == n];
for (int i = 1; i <= n; i++)
cout << i << ' ';
}
signed main()
{
if (fopen("in.txt", "r"))
{
freopen("in.txt", "r", stdin);
freopen("ans.txt", "w", stdout);
}
else if (fopen(name".inp", "r"))
{
freopen(name".inp", "r", stdin);
freopen(name".out", "w", stdout);
}
ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
int tc = 1;
// cin >> tc;
while (tc--)
solve();
}
