Problem: This problem is split into two tasks. In this task, you are required to find the minimum possible answer. In the task Village (Maximum) you are required to find the maximum possible answer. Each task is worth 50 points.

There are N houses in a certain village. A single villager lives in each of the houses. The houses are connected by roads. Each road connects two houses and is exactly 1 kilometer long. From each house it is possible to reach any other using one or several consecutive roads. In total there are N-1 roads in the village.

One day all villagers decided to move to different houses — that is, after moving each house should again have a single villager living in it, but no villager should be living in the same house as before. We would like to know the smallest possible total length in kilometers of the shortest paths between the old and the new houses for all villagers.

<image>

Example village with seven houses 

For example, if there are seven houses connected by roads as shown on the figure, the smallest total length is 8 km (this can be achieved by moving 1 → 6, 2 → 4, 3 → 1, 4 → 2, 5 → 7, 6 → 3, 7 → 5).

Write a program that finds the smallest total length of the shortest paths in kilometers and an example assignment of the new houses to the villagers.

Input

The first line contains an integer N (1 < N ≤ 10^5). Houses are numbered by consecutive integers 1, 2, …, N.

Then N-1 lines follow that describe the roads. Each line contains two integers a and b (1 ≤ a, b ≤ N, a ≠ b) denoting that there is a road connecting houses a and b.

Output

In the first line output the smallest total length of the shortest paths in kilometers.

In the second line describe one valid assignment of the new houses with the smallest total length: N space-separated distinct integers v_1, v_2, …, v_N. For each i, v_i is the house number where the villager from the house i should move (v_i ≠ i). If there are several valid assignments, output any of those.

Scoring

Subtasks: 

  1. (6 points) N ≤ 10 
  2. (19 points) N ≤ 1 000 
  3. (25 points) No further constraints 

Examples

Input


4
1 2
2 3
3 4


Output


4
2 1 4 3


Input


7
4 2
5 7
3 4
6 3
1 3
4 5


Output


8
3 4 6 2 7 1 5

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
template <class c>
int popc(c a) {
  if (sizeof(c) == 8)
    return __builtin_popcountll(a);
  else
    return __builtin_popcount(a);
}
template <class c>
int ctz(c a) {
  if (sizeof(c) == 8)
    return __builtin_ctzll(a);
  else
    return __builtin_ctz(a);
}
template <class c>
int clz(c a) {
  if (sizeof(c) == 8)
    return __builtin_clzll(a);
  else
    return __builtin_clz(a);
}
inline int min(const int &first, const int &second) {
  return (((second - first) >> (32 - 1)) & (first ^ second)) ^ first;
}
inline int max(const int &first, const int &second) {
  return (((second - first) >> (32 - 1)) & (first ^ second)) ^ second;
}
inline long long min(const long long &first, const long long &second) {
  return (((second - first) >> (64 - 1)) & (first ^ second)) ^ first;
}
inline long long max(const long long &first, const long long &second) {
  return (((second - first) >> (64 - 1)) & (first ^ second)) ^ second;
}
using namespace std;
char string_in_buffer[(int)260];
void fast_scan(int &first) { scanf("%d", &first); }
void fast_scan(long long &first) { scanf("%lld", &first); }
void fast_scan(unsigned long long &first) { scanf("%llu", &first); }
void fast_scan(double &first) { scanf("%lf", &first); }
void fast_scan(long double &first) { scanf("%Lf", &first); }
void fast_scan(char &first) {
  scanf("%c", &first);
  if (first == '\n') {
    fast_scan(first);
  }
}
void fast_scan(string &first) {
  scanf("%s", string_in_buffer);
  first = string(string_in_buffer);
}
template <class TFirst, class TSecond>
void fast_scan(pair<TFirst, TSecond> &p) {
  fast_scan(p.first);
  fast_scan(p.second);
}
template <class T>
void fast_scan(vector<T> &v) {
  for (auto &first : v) fast_scan(first);
}
void fast_print(const int &first) { printf("%d", first); }
void fast_print(const unsigned int &first) { printf("%u", first); }
void fast_print(const long long &first) { printf("%lld", first); }
void fast_print(const unsigned long long &first) { printf("%llu", first); }
void fast_print(const char &first) { printf("%c", first); };
void fast_print(const double &first) { printf("%.15lf", first); }
void fast_print(const long double &first) { printf("%.15Lf", first); }
void fast_print(const string &first) { printf("%s", first.c_str()); }
void fast_print(const char v[]) { fast_print((string)v); }
template <class TFirst, class TSecond>
void fast_print(const pair<TFirst, TSecond> &p) {
  fast_print(p.first);
  fast_print(' ');
  fast_print(p.second);
}
template <class T>
void fast_print(const vector<T> &v) {
  if (v.empty()) return;
  fast_print(v[0]);
  for (int i = 1; i < v.size(); i++) {
    fast_print(' ');
    fast_print(v[i]);
  }
}
template <class T>
void fast_print(const vector<vector<T>> &v) {
  if (v.empty()) return;
  fast_print(v[0]);
  for (int i = 1; i < v.size(); i++) {
    fast_print('\n');
    fast_print(v[i]);
  }
}
template <class T>
void fast_print(const T &v) {
  for (const auto &first : v) {
    fast_print(first);
    fast_print(' ');
  }
}
using namespace std;
namespace smart_io {
string print_start = "";
string sep = " ";
bool first_print = false;
void precall_print() {
  fast_print(print_start);
  print_start = "\n";
  first_print = true;
}
void _print(deque<string>) {}
template <class T, class... Args>
void _print(deque<string> names, T elem, Args... args) {
  if (!first_print) {
    fast_print("\n");
  } else {
    first_print = false;
  }
  fast_print(names.front());
  fast_print(" = ");
  fast_print(elem);
  names.pop_front();
  _print(names, args...);
}
}  // namespace smart_io
template <class T>
ostream &operator,(ostream &os, const T &object) {
  if (!smart_io::first_print) {
    fast_print(smart_io::sep);
  } else {
    smart_io::first_print = false;
  }
  fast_print(object);
  return os;
}
template <class T>
istream &operator,(istream &is, T &object) {
  fast_scan(object);
  return is;
}
namespace escape__from__random__aetuhoetnuhshe {
using namespace std::chrono;
mt19937 rng(duration_cast<milliseconds>(system_clock::now().time_since_epoch())
                .count());
uniform_real_distribution<> prob_dist(0.0, 1.0);
};  // namespace escape__from__random__aetuhoetnuhshe
namespace typedefs {}
namespace numbers_operation {
template <class T>
inline T floor_mod(T a, const T &b) {
  a %= b;
  if (a < 0) a += b;
  return a;
}
}  // namespace numbers_operation
using namespace numbers_operation;
using namespace typedefs;
using namespace escape__from__random__aetuhoetnuhshe;
int n;
vector<vector<int>> g;
vector<int> tsize;
void dfs0(int v, int _p) {
  tsize[v] = 1;
  for (int sub : g[v]) {
    if (sub == _p) continue;
    dfs0(sub, v);
    tsize[v] += tsize[sub];
  }
}
long long S = 0;
void dfs1(int v, int _p, int up) {
  for (int sub : g[v]) {
    if (sub == _p) continue;
    S += 2 * min(tsize[sub], tsize[v] + up - tsize[sub]);
    dfs1(sub, v, tsize[v] + up - tsize[sub]);
  }
}
struct Tree {
  int n;
  vector<int> _lca;
  vector<vector<int>> g, h;
  vector<int> tin, tout, tsize, pref, depth, head, tour;
  void dfs0(int v, int _p) {
    tsize[v] = 1;
    pref[v] = _p;
    for (int sub : g[v]) {
      if (sub == _p) continue;
      h[v].push_back(sub);
      depth[sub] = depth[v] + 1;
      dfs0(sub, v);
      tsize[v] += tsize[sub];
    }
    for (int j = 0; j < ((int)h[v].size()); j++)
      if (tsize[h[v][j]] > tsize[h[v][0]]) swap(h[v][j], h[v][0]);
  }
  void dfs1(int v, int &timer, int d) {
    tin[v] = timer++, head[v] = d;
    tour.push_back(v);
    if (!h[v].empty()) dfs1(h[v][0], timer, d);
    for (int j = 1; j < ((int)h[v].size()); j++) {
      int sub = h[v][j];
      dfs1(sub, timer, sub);
    }
    tout[v] = timer;
  }
  void init(vector<vector<int>> _g) {
    g = _g;
    n = ((int)g.size());
    tin.clear(), tout.clear(), tsize.clear(), h.clear(), pref.clear(),
        depth.clear(), _lca.clear(), head.clear(), tour.clear();
    tin.resize(n), tout.resize(n), tsize.resize(n), h.resize(n), pref.resize(n),
        depth.resize(n), head.resize(n);
    dfs0(0, -1);
    int timer = 0;
    dfs1(0, timer, 0);
    int t = 31 - __builtin_clz(n) + 1;
    _lca.resize(t * n);
    for (int i = 0; i < n; i++) _lca[tin[i]] = i;
    for (int i = 1; i < t; i++) {
      for (int j = 0; j < n; j++) {
        _lca[i * n + j] = _lca[(i - 1) * n + j];
        int k = j + (1 << (i - 1));
        if (k < n && depth[_lca[(i - 1) * n + k]] <= depth[_lca[i * n + j]])
          _lca[i * n + j] = _lca[(i - 1) * n + k];
      }
    }
  }
  bool anc(int v, int u) { return tin[v] <= tin[u] && tout[u] <= tout[v]; }
  int get_subtree_size(int v, int root) {
    if (anc(v, root)) {
      return n - tsize[next(v, root)];
    } else
      return tsize[v];
  }
  pair<int, int> get_range(int v) { return make_pair(tin[v], tout[v]); }
  int lca(int a, int b) {
    if (anc(a, b)) return a;
    if (anc(b, a)) return b;
    a = tin[a], b = tin[b];
    if (a > b) swap(a, b);
    int p = 31 - __builtin_clz(b - a + 1);
    a = _lca[p * n + a];
    b = _lca[p * n + b - (1 << p) + 1];
    return pref[(depth[a] < depth[b]) ? a : b];
  }
  int jump(int v, int k) {
    while (v != -1) {
      int u = head[v];
      if (k <= depth[v] - depth[u]) {
        return tour[tin[v] - k];
      } else {
        k -= depth[v] - depth[u] + 1;
        v = pref[u];
      }
    }
    assert(false);
  }
  int next(int a, int b) {
    if (a == b) return a;
    if (anc(a, b)) {
      a = tin[a] + 1, b = tin[b];
      int p = 31 - __builtin_clz(b - a + 1);
      a = _lca[p * n + a];
      b = _lca[p * n + b - (1 << p) + 1];
      return depth[a] < depth[b] ? a : b;
    } else
      return pref[a];
  }
  int dist(int a, int b) { return depth[a] + depth[b] - 2 * depth[lca(a, b)]; }
  vector<pair<int, int>> decompose_up(int up, int down) {
    vector<pair<int, int>> ranges;
    while (head[down] != head[up]) {
      ranges.emplace_back(tin[down], tin[head[down]]);
      down = pref[head[down]];
    }
    if (up != down) ranges.emplace_back(tin[down], tin[up] + 1);
    return ranges;
  }
  vector<pair<int, int>> decompose(int a, int b, bool include_lca) {
    int c = lca(a, b);
    vector<pair<int, int>> path = decompose_up(c, a);
    if (include_lca) path.emplace_back(tin[c], tin[c]);
    vector<pair<int, int>> end = decompose_up(c, b);
    for (int i = ((int)end.size()) - 1; ~i; i--)
      path.emplace_back(end[i].second, end[i].first);
    return path;
  }
};
struct CentroidTree : public Tree {
  int estimate_size(int v, int _p, const vector<bool> &used) {
    int sz = 1;
    for (int sub : g[v]) {
      if (sub == _p) continue;
      if (used[sub]) continue;
      sz += estimate_size(sub, v, used);
    }
    return sz;
  }
  int collect_centroids(int v, int _p, const int &N, int &C1, int &C2,
                        const vector<bool> &used) {
    int sz = 1;
    bool centroid = true;
    for (int sub : g[v]) {
      if (sub == _p) continue;
      if (!used.empty() && used[sub]) continue;
      int t = collect_centroids(sub, v, N, C1, C2, used);
      if (2 * t > N) centroid = false;
      sz += t;
    }
    if (centroid && sz * 2 >= N) {
      if (C1 == -1)
        C1 = v;
      else
        C2 = v;
    }
    return sz;
  }
  vector<int> find_centroids(int traverse, const vector<bool> &used) {
    int a = -1, b = -1;
    collect_centroids(traverse, -1,
                      used.empty() ? n : estimate_size(traverse, -1, used), a,
                      b, used);
    vector<int> rez;
    if (a != -1) rez.push_back(a);
    if (b != -1) rez.push_back(b);
    return rez;
  }
  vector<int> find_centroids() { return find_centroids(0, {}); }
};
void collect(int v, int _p, vector<int> &nodes) {
  nodes.push_back(v);
  for (int sub : g[v]) {
    if (sub == _p) continue;
    collect(sub, v, nodes);
  }
}
signed main(signed argc, char *argv[]) {
  cin, n;
  g.resize(n);
  for (int i = 0; i < (n - 1); i++) {
    int a, b;
    cin, a, b;
    a--;
    b--;
    g[a].push_back(b);
    g[b].push_back(a);
  }
  tsize.resize(n);
  dfs0(0, -1);
  dfs1(0, -1, 0);
  smart_io::precall_print();
  cout, S;
  CentroidTree tree;
  tree.init(g);
  vector<int> c = tree.find_centroids();
  if (((int)c.size()) == 2) {
    vector<int> parts[2];
    collect(c[0], c[1], parts[0]);
    collect(c[1], c[0], parts[1]);
    assert(((int)parts[0].size()) == ((int)parts[1].size()));
    vector<int> next(n);
    for (int i = 0; i < ((int)parts[0].size()); i++) {
      next[parts[0][i]] = parts[1][i];
      next[parts[1][i]] = parts[0][i];
    }
    for (auto &first : next) {
      first++;
    }
    smart_io::precall_print();
    cout, next;
  } else {
    vector<int> all;
    collect(c[0], -1, all);
    vector<int> next(n);
    for (int i = 0; i < ((int)all.size()); i++) {
      next[all[i]] = all[(i + ((int)all.size()) / 2) % ((int)all.size())];
    }
    for (auto &first : next) {
      first++;
    }
    smart_io::precall_print();
    cout, next;
  }
}