#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int MAX_N = 100005;
vector<int>adj[MAX_N];
int visited[MAX_N],ans;
int order[MAX_N],cnt=1;
void dfs(int s, int p) {
for(int u : adj[s]) {
if(u == p) continue;
dfs(u,s);
}
if(!visited[s] and !visited[p] and s and p) {
visited[s] = p;
visited[p] = s;
ans+=2;
}
}
void dfs2(int s, int p) {
order[cnt++] = s;
for(int u : adj[s]) {
if(u == p) continue;
dfs2(u,s);
}
}
void solve() {
int n; cin >> n;
for(int i=0; i<n-1; i++) {
int a,b; cin >> a >> b;
adj[a].push_back(b);
adj[b].push_back(a);
}
dfs(1,0);
for(int i=1; i<=n; i++) {
if(!visited[i]) {
visited[i] = i;
swap(visited[i], visited[adj[i][0]]);
ans+=2;
}
}
cout << ans << " " << ans << endl;
for(int i=1; i<=n; i++) cout << visited[i] << " ";
cout << endl;
dfs2(1,0);
for(int i=1; i<=n; i++) {
int tmp = (i+n/2)%n;
if(tmp == 0) tmp = n;
cout << order[tmp] << " ";
}
cout << endl;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
int t=1;
while(t--) solve();
}
