#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;
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 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;
for(int i=1; i<=n; i++) cout << i << " ";
cout << endl;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
int t=1;
while(t--) solve();
}
