#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> v;
typedef vector<v> vv;
typedef vector<vv> vvv;
typedef pair<ll, ll> p;
typedef vector<p> vp;
typedef vector<vp> vvp;
typedef vector<vvp> vvvp;
typedef pair<ll, p> tri;
typedef vector<tri> vtri;
typedef vector<vtri> vvtri;
typedef vector<vvtri> vvvtri;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<vvb> vvvb;
#define f first
#define s second
#define pb push_back
#define eb emplace_back
#define all(v) (v).begin(),(v).end()
const ll INF = 1e12;
const ll mod = 1e9 + 7;
int main()
{
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
ll N;
cin >> N;
vv graph(N);
for (ll i = 0; i < N - 1; i++)
{
ll a, b;
cin >> a >> b; a--; b--;
graph[a].pb(b);
graph[b].pb(a);
}
vv distance(N, v(N));
for (ll i =0 ; i < N; i++)
{
vb visited(N, false);
stack<p> dfs;
dfs.emplace(i, 0);
while (!dfs.empty())
{
auto top = dfs.top();
dfs.pop();
if (visited[top.f]) continue;
visited[top.f] = true;
distance[i][top.f] = top.s;
for (ll x : graph[top.f]) dfs.emplace(x, top.s + 1);
}
}
v perm(N);
for (ll i =0 ; i < N; i++) perm[i] = i;
ll mini = INF, maxi = -INF;
vv miniPerms, maxiPerms;
do
{
bool valid = true;
for (ll i= 0 ; i < N; i++) if (perm[i] == i) valid = false;
if (!valid) continue;
ll ev = 0;
for (ll i = 0; i < N; i++) ev += distance[i][perm[i]];
if (ev < mini)
{
mini = ev;
v newPerm(N);
copy(all(perm), newPerm.begin());
miniPerms = {newPerm};
}
else if (ev == mini)
{
v newPerm(N);
copy(all(perm), newPerm.begin());
miniPerms.pb(newPerm);
}
if (ev > maxi)
{
maxi = ev;
v newPerm(N);
copy(all(perm), newPerm.begin());
maxiPerms = {newPerm};
}
else if (ev == maxi)
{
v newPerm(N);
copy(all(perm), newPerm.begin());
maxiPerms.pb(newPerm);
}
}
while (next_permutation(all(perm)));
bool valid = false;
for (v perm : miniPerms)
{
vb visited(N, false);
bool cur = true;
for (ll i= 0; i < N; i++)
{
if (visited[i]) continue;
ll start = perm[i]; visited[start] = true;
ll cnt = 1;
while (start != i)
{
start = perm[start];
visited[start] = true;
cnt++;
}
if (cnt > 3) cur = false;
}
if (cur) valid = true;
}
assert(valid);
cout << mini << " " << maxi << "\n";
for (ll x : miniPerms[0]) cout << x + 1 << " ";
cout << "\n";
for (ll x : maxiPerms[0]) cout << x + 1 << " ";
cout << "\n";
}
