Problem: There are N cities in Bob's country connected by roads. Some pairs of cities are connected by public transport. There are two competing transport companies — Boblines operating buses and Bobrail running trains. When traveling from A to B, a passenger always first selects the mode of transport (either bus or train), and then embarks on a journey. For every pair of cities, there are exactly two ways of how to travel between them without visiting any city more than once — one using only bus routes, and the second using only train routes. Furthermore, there is no pair of cities that is directly connected by both a bus route and a train route.

You obtained the plans of each of the networks. Unfortunately, each of the companies uses different names for the same cities. More precisely, the bus company numbers the cities using integers from 1 to N, while the train company uses integers between N + 1 and 2N. Find one possible mapping between those two numbering schemes, such that no pair of cities is connected directly by both a bus route and a train route. Note that this mapping has to map different cities to different cities.

Input

The first line contains an integer N (2 ≤ N ≤ 10000), the number of cities.

N - 1 lines follow, representing the network plan of Boblines. Each contains two integers u and v (1 ≤ u, v ≤ N), meaning that there is a bus route between cities u and v.

N - 1 lines follow, representing the network plan of Bobrail. Each contains two integers u and v (N + 1 ≤ u, v ≤ 2N), meaning that there is a train route between cities u and v.

Output

If there is no solution, output a single line with the word "No".

If a solution exists, output two lines. On the first line, there should be the word "Yes". On the second line, there should be N integers P1, P2, ..., PN (N + 1 ≤ Pi ≤ 2N) — the mapping between the two numbering schemes. More precisely, for i ≠ j it should be Pi ≠ Pj, and for every direct bus route (i, j), there is no direct train route between (Pi, Pj).

If there are multiple solutions, you may print any of them.

Examples

Input

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


Output

Yes
6 8 5 7


Input

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


Output

No


Input

7
1 2
1 3
1 4
1 5
5 6
6 7
8 9
9 10
10 11
11 12
12 13
13 14


Output

Yes
9 14 11 12 13 10 8

Note

The first sample (bus lines in red and rail lines in blue):

<image>

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
using Pair = pair<int, int>;
struct Graph {
  int n;
  set<Pair> edges;
  set<int> current_vert;
  vector<set<int>> graph;
  vector<int> ng;
  set<Pair> leafs;
  set<Pair> st_to_v;
  Graph() {}
  Graph(int _n, vector<Pair>& v_edges) {
    n = _n;
    graph.resize(n);
    ng.assign(n, 0);
    for (auto e : v_edges) {
      edges.emplace(e);
      edges.emplace(e.second, e.first);
      graph[e.first].insert(e.second);
      graph[e.second].insert(e.first);
      ng[e.first]++;
      ng[e.second]++;
    }
    for (int i = 0; i < n; ++i) current_vert.insert(i);
    for (int i = 0; i < n; ++i) {
      if (ng[i] == 1) leafs.insert(Pair(*graph[i].begin(), i));
      st_to_v.insert(Pair(ng[i], i));
    }
  }
  int max_st_v() const { return st_to_v.rbegin()->second; }
  bool is_k_start(int k) const { return st_to_v.rbegin()->first == n - 1 - k; }
  void erase_leaf(int v) {
    --n;
    current_vert.erase(v);
    leafs.erase(Pair(*graph[v].begin(), v));
    st_to_v.erase(Pair(ng[v], v));
    for (int x : graph[v]) {
      graph[x].erase(v);
      st_to_v.erase(Pair(ng[x], x));
      ng[x]--;
      st_to_v.insert(Pair(ng[x], x));
      if (ng[x] == 1) leafs.insert(Pair(*graph[x].begin(), x));
    }
  }
  Pair get_leaf_pair() const {
    int a = leafs.begin()->second;
    int b = leafs.rbegin()->second;
    return Pair(a, b);
  }
  Pair get_non_star_pair() const {
    set<Pair> tmp;
    tmp.insert(*leafs.begin());
    tmp.insert(*(++leafs.begin()));
    tmp.insert(*leafs.rbegin());
    tmp.insert(*(++leafs.rbegin()));
    int pref = -1;
    for (auto p : tmp) {
      if (ng[p.first] > 2) pref = p.first;
    }
    if (pref == -1) {
      int a = leafs.begin()->second;
      int b = leafs.rbegin()->second;
      return Pair(a, b);
    }
    Pair a;
    Pair b;
    for (auto p : tmp) {
      if (p.first == pref)
        a = p;
      else
        b = p;
    }
    return Pair(a.second, b.second);
  }
  int get_prev(int v) const { return *graph[v].begin(); }
  bool check_edge(Pair edge) const { return edges.count(edge); }
};
using Map = unordered_map<int, int>;
class Solver {
  static Map rev_map(const Map& map) {
    Map res;
    for (auto a : map) res[a.second] = a.first;
    return res;
  }
  Map solve_small(Graph& a, Graph& b) {
    auto av = a.current_vert;
    auto bv = b.current_vert;
    vector<int> avv;
    vector<int> bvv;
    for (int x : av) avv.push_back(x);
    for (int x : bv) bvv.push_back(x);
    const int n = avv.size();
    do {
      bool ok = true;
      for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
          Pair ea(avv[i], avv[j]);
          Pair eb(bvv[i], bvv[j]);
          if (ok && a.check_edge(ea) && b.check_edge(eb)) ok = false;
        }
      }
      if (ok) {
        Map res;
        for (int i = 0; i < n; ++i) res[avv[i]] = bvv[i];
        return res;
      }
    } while (std::next_permutation(avv.begin(), avv.end()));
    return Map();
  }
  Map solve_1_star(Graph& a, Graph& b) {
    auto av = a.current_vert;
    int wa = a.max_st_v();
    int ua = -1;
    int va = -1;
    for (int x : av) {
      if (x == wa || a.check_edge(Pair(x, wa))) continue;
      va = x;
      ua = a.get_prev(va);
      break;
    }
    av.erase(wa);
    av.erase(ua);
    av.erase(va);
    auto bv = b.current_vert;
    Pair pp = b.get_leaf_pair();
    int wb = pp.first;
    int vb = pp.second;
    int ub = b.get_prev(wb);
    bv.erase(wb);
    bv.erase(ub);
    bv.erase(vb);
    Map res;
    res[wa] = wb;
    res[ua] = vb;
    res[va] = ub;
    for (int x : av) {
      res[x] = *bv.begin();
      bv.erase(bv.begin());
    }
    return res;
  }
  void solve(Map& res, Graph& a, Graph& b) {
    if (a.is_k_start(1)) {
      res = solve_1_star(a, b);
      return;
    }
    if (b.is_k_start(1)) {
      res = solve_1_star(b, a);
      res = rev_map(res);
      return;
    }
    if (a.n <= 5) {
      res = solve_small(a, b);
      return;
    }
    Pair pa = a.get_non_star_pair();
    Pair ppa(a.get_prev(pa.first), a.get_prev(pa.second));
    a.erase_leaf(pa.first);
    a.erase_leaf(pa.second);
    Pair pb = b.get_non_star_pair();
    Pair ppb(b.get_prev(pb.first), b.get_prev(pb.second));
    b.erase_leaf(pb.first);
    b.erase_leaf(pb.second);
    solve(res, a, b);
    if (res[ppa.first] != ppb.first && res[ppa.second] != ppb.second) {
      res[pa.first] = pb.first;
      res[pa.second] = pb.second;
    } else {
      res[pa.first] = pb.second;
      res[pa.second] = pb.first;
    }
  }

 public:
  Solver() {}
  void solve(istream& in, ostream& out) {
    int n;
    in >> n;
    vector<Pair> edges_a(n - 1);
    vector<Pair> edges_b(n - 1);
    for (Pair& p : edges_a) {
      in >> p.first >> p.second;
      --p.first;
      --p.second;
    }
    for (Pair& p : edges_b) {
      in >> p.first >> p.second;
      p.first -= n + 1;
      p.second -= n + 1;
    }
    Graph a(n, edges_a);
    Graph b(n, edges_b);
    if (a.is_k_start(0) || b.is_k_start(0)) {
      out << "No" << endl;
      return;
    }
    unordered_map<int, int> res;
    solve(res, b, a);
    res = rev_map(res);
    out << "Yes" << endl;
    for (int i = 0; i < n; ++i) out << res[i] + 1 + n << " ";
    out << endl;
  }
};
mt19937 rnd(1);
string gen_test() {
  int n = 2 + rnd() % 10;
  ostringstream out;
  out << n << endl;
  vector<int> shuffle_a(n);
  for (int i = 0; i < n; ++i) shuffle_a[i] = i + 1;
  std::shuffle(shuffle_a.begin(), shuffle_a.end(), rnd);
  vector<int> shuffle_b(n);
  for (int i = 0; i < n; ++i) shuffle_b[i] = i + n + 1;
  std::shuffle(shuffle_b.begin(), shuffle_b.end(), rnd);
  vector<int> p(n);
  for (int i = 1; i < n; ++i) {
    p[i] = rnd() % i;
    out << shuffle_a[i] << ' ' << shuffle_a[p[i]] << endl;
  }
  for (int i = 1; i < n; ++i) {
    p[i] = rnd() % i;
    out << shuffle_b[i] << ' ' << shuffle_b[p[i]] << endl;
  }
  return out.str();
}
class StSolver {
  int n;
  set<Pair> ed;
  vector<int> res;
  bool check() {
    for (Pair e : ed) {
      if (e.first <= n) {
        Pair eb(res[e.first - 1], res[e.second - 1]);
        if (ed.count(eb)) return false;
      }
    }
    return true;
  }

 public:
  void solve(istream& in, ostream& out) {
    in >> n;
    for (int i = 0; i < (n - 1) * 2; ++i) {
      int a, b;
      in >> a >> b;
      ed.insert(Pair(a, b));
      ed.insert(Pair(b, a));
    }
    for (int i = n + 1; i <= 2 * n; ++i) {
      res.push_back(i);
    }
    do {
      if (check()) {
        out << "Yes";
        return;
      }
    } while (std::next_permutation(res.begin(), res.end()));
    out << "No";
  }
};
class Checker {
  int n;
  set<Pair> ed;
  vector<int> res;
  bool check() {
    for (Pair e : ed) {
      if (e.first <= n) {
        Pair eb(res[e.first - 1], res[e.second - 1]);
        if (ed.count(eb)) return false;
      }
    }
    return true;
  }

 public:
  bool check(istream& in, istream& rr) {
    in >> n;
    for (int i = 0; i < (n - 1) * 2; ++i) {
      int a, b;
      in >> a >> b;
      ed.insert(Pair(a, b));
      ed.insert(Pair(b, a));
    }
    {
      string _;
      rr >> _;
    }
    res.resize(n);
    for (int& x : res) rr >> x;
    return check();
  }
};
void test() {
  for (int it = 0; it < 10000; ++it) {
    cerr << "Test " << it << endl;
    string test = gen_test();
    string res;
    string res2;
    {
      istringstream is(test);
      ostringstream os;
      Solver().solve(is, os);
      res = os.str();
    }
    {
      istringstream is(test);
      ostringstream os;
      StSolver().solve(is, os);
      res2 = os.str();
    }
    if (res2[0] == 'Y') {
      istringstream is(test);
      istringstream is2(res);
      if (!Checker().check(is, is2)) {
        cerr << "Bad test" << endl;
        cerr << test << endl;
        cerr << res << endl;
        for (char c : test) {
          if (c == '\n')
            cerr << "\\n";
          else
            cerr << c;
        }
        cerr << endl;
        exit(1);
      }
    }
    if (res2[0] != res[0]) {
      cerr << "Bad test" << endl;
      cerr << test << endl;
      exit(0);
    }
  }
  exit(0);
}
int main() {
  std::ios_base::sync_with_stdio(false);
  Solver().solve(std::cin, std::cout);
}