#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl "\n"
const int MOD = 998244353;
vector<int> v;
int ans = 0;
bool DFS(int x, vector<vector<int>>& adj, int p){
vector<int> odd;
for(int node : adj[x]){
if(node == p) continue;
bool rep = DFS(node, adj, x);
if(rep) odd.push_back(node);
}
if(odd.size() == 0){
if(x == 0){
int node = adj[x][0];
if(v[v[node]] == node){
v[x] = v[node];
v[node] = x;
ans += 2;
}else{
int node1 = v[node];
int node2 = v[v[node]];
v[node1] = node2;
v[node2] = node1;
v[x] = node;
v[node] = x;
ans += 2;
}
}else return 1;
}else{
if(((int)odd.size()) % 2 == 1){
for(int i = 1; i < (int)odd.size() - 1; i += 2){
v[odd[i]] = odd[i + 1];
v[odd[i + 1]] = odd[i];
ans += 4;
}
v[x] = odd[0];
v[odd[0]] = x;
ans += 2;
}else{
for(int i = 2; i < (int)odd.size() - 1; i += 2){
v[odd[i]] = odd[i + 1];
v[odd[i + 1]] = odd[i];
ans += 4;
}
v[x] = odd[0];
v[odd[0]] = odd[1];
v[odd[1]] = x;
ans += 4;
}
}
return 0;
}
void solve(){
int n; cin >> n;
v.resize(n);
vector<vector<int>> adj(n);
for(int i = 0; i < n - 1; i++){
int a, b; cin >> a >> b; a--; b--;
adj[a].push_back(b); adj[b].push_back(a);
}
DFS(0, adj, -1);
cout << ans << " "<<-1 << endl;
for(int x : v) cout << x + 1 << " ";
cout << endl;
for(int i = 0; i < n; i++) cout << 1 << " ";
cout << endl;
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
//freopen("inpt.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
//int tt; cin >> tt;
int tt = 1;
for(int t = 1; t <= tt; t++){
//cout << "Case #"<<t << ": ";
solve();
}
}
