Problem: Donghyun's new social network service (SNS) contains n users numbered 1, 2, …, n. Internally, their network is a tree graph, so there are n-1 direct connections between each user. Each user can reach every other users by using some sequence of direct connections. From now on, we will denote this primary network as T_1.

To prevent a possible server breakdown, Donghyun created a backup network T_2, which also connects the same n users via a tree graph. If a system breaks down, exactly one edge e ∈ T_1 becomes unusable. In this case, Donghyun will protect the edge e by picking another edge f ∈ T_2, and add it to the existing network. This new edge should make the network be connected again. 

Donghyun wants to assign a replacement edge f ∈ T_2 for as many edges e ∈ T_1 as possible. However, since the backup network T_2 is fragile, f ∈ T_2 can be assigned as the replacement edge for at most one edge in T_1. With this restriction, Donghyun wants to protect as many edges in T_1 as possible.

Formally, let E(T) be an edge set of the tree T. We consider a bipartite graph with two parts E(T_1) and E(T_2). For e ∈ E(T_1), f ∈ E(T_2), there is an edge connecting \\{e, f\} if and only if graph T_1 - \\{e\} + \\{f\} is a tree. You should find a maximum matching in this bipartite graph.

Input

The first line contains an integer n (2 ≤ n ≤ 250 000), the number of users. 

In the next n-1 lines, two integers a_i, b_i (1 ≤ a_i, b_i ≤ n) are given. Those two numbers denote the indices of the vertices connected by the corresponding edge in T_1.

In the next n-1 lines, two integers c_i, d_i (1 ≤ c_i, d_i ≤ n) are given. Those two numbers denote the indices of the vertices connected by the corresponding edge in T_2. 

It is guaranteed that both edge sets form a tree of size n.

Output

In the first line, print the number m (0 ≤ m < n), the maximum number of edges that can be protected.

In the next m lines, print four integers a_i, b_i, c_i, d_i. Those four numbers denote that the edge (a_i, b_i) in T_1 is will be replaced with an edge (c_i, d_i) in T_2.

All printed edges should belong to their respective network, and they should link to distinct edges in their respective network. If one removes an edge (a_i, b_i) from T_1 and adds edge (c_i, d_i) from T_2, the network should remain connected. The order of printing the edges or the order of vertices in each edge does not matter.

If there are several solutions, you can print any.

Examples

Input


4
1 2
2 3
4 3
1 3
2 4
1 4


Output


3
3 2 4 2
2 1 1 3
4 3 1 4


Input


5
1 2
2 4
3 4
4 5
1 2
1 3
1 4
1 5


Output


4
2 1 1 2
3 4 1 3
4 2 1 4
5 4 1 5


Input


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


Output


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

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template <class t, class u>
void chmax(t& first, u second) {
  if (first < second) first = second;
}
template <class t, class u>
void chmin(t& first, u second) {
  if (second < first) first = second;
}
template <class t>
using vc = vector<t>;
template <class t>
using vvc = vc<vc<t>>;
using pi = pair<int, int>;
using vi = vc<int>;
template <class t, class u>
ostream& operator<<(ostream& os, const pair<t, u>& p) {
  return os << "{" << p.first << "," << p.second << "}";
}
template <class t>
ostream& operator<<(ostream& os, const vc<t>& v) {
  os << "{";
  for (auto e : v) os << e << ",";
  return os << "}";
}
using uint = unsigned;
using ull = unsigned long long;
template <class t, size_t n>
ostream& operator<<(ostream& os, const array<t, n>& first) {
  return os << vc<t>(first.begin(), first.end());
}
template <int i, class T>
void print_tuple(ostream&, const T&) {}
template <int i, class T, class H, class... Args>
void print_tuple(ostream& os, const T& t) {
  if (i) os << ",";
  os << get<i>(t);
  print_tuple<i + 1, T, Args...>(os, t);
}
template <class... Args>
ostream& operator<<(ostream& os, const tuple<Args...>& t) {
  os << "{";
  print_tuple<0, tuple<Args...>, Args...>(os, t);
  return os << "}";
}
template <class t>
void print(t x, int suc = 1) {
  cout << x;
  if (suc == 1) cout << "\n";
  if (suc == 2) cout << " ";
}
ll read() {
  ll i;
  cin >> i;
  return i;
}
vi readvi(int n, int off = 0) {
  vi v(n);
  for (int i = int(0); i < int(n); i++) v[i] = read() + off;
  return v;
}
template <class T>
void print(const vector<T>& v, int suc = 1) {
  for (int i = int(0); i < int(v.size()); i++)
    print(v[i], i == int(v.size()) - 1 ? suc : 2);
}
string readString() {
  string s;
  cin >> s;
  return s;
}
template <class T>
T sq(const T& t) {
  return t * t;
}
void yes(bool ex = true) {
  cout << "Yes"
       << "\n";
  if (ex) exit(0);
}
void no(bool ex = true) {
  cout << "No"
       << "\n";
  if (ex) exit(0);
}
void possible(bool ex = true) {
  cout << "Possible"
       << "\n";
  if (ex) exit(0);
}
void impossible(bool ex = true) {
  cout << "Impossible"
       << "\n";
  if (ex) exit(0);
}
constexpr ll ten(int n) { return n == 0 ? 1 : ten(n - 1) * 10; }
const ll infLL = LLONG_MAX / 3;
const int inf = INT_MAX / 2 - 100;
int topbit(signed t) { return t == 0 ? -1 : 31 - __builtin_clz(t); }
int topbit(ll t) { return t == 0 ? -1 : 63 - __builtin_clzll(t); }
int botbit(signed first) { return first == 0 ? 32 : __builtin_ctz(first); }
int botbit(ll first) { return first == 0 ? 64 : __builtin_ctzll(first); }
int popcount(signed t) { return __builtin_popcount(t); }
int popcount(ll t) { return __builtin_popcountll(t); }
bool ispow2(int i) { return i && (i & -i) == i; }
int mask(int i) { return (int(1) << i) - 1; }
bool inc(int first, int second, int c) {
  return first <= second && second <= c;
}
template <class t>
void mkuni(vc<t>& v) {
  sort(v.begin(), v.end());
  v.erase(unique(v.begin(), v.end()), v.end());
}
ll rand_int(ll l, ll r) {
  static random_device rd;
  static mt19937_64 gen(rd());
  return uniform_int_distribution<ll>(l, r)(gen);
}
template <class t>
int lwb(const vc<t>& v, const t& first) {
  return lower_bound(v.begin(), v.end(), first) - v.begin();
}
template <class N>
struct linkcut {
  struct Node {
    using np = Node*;
    np l, r, p;
    bool rev;
    N x;
    Node() : l(0), r(0), p(0), rev(false), x() {}
    void reverse() {
      rev ^= true;
      x.reverse();
    }
    void propagate() {
      if (rev) {
        swap(l, r);
        if (l) l->reverse();
        if (r) r->reverse();
        rev = false;
      }
      if (l) x.push(l->x);
      if (r) x.push(r->x);
      x.clear();
    }
    void update() {
      x.single();
      if (l) x.updatel(l->x);
      if (r) x.updater(r->x);
    }
    int pos() {
      if (p && p->l == this) return -1;
      if (p && p->r == this) return 1;
      return 0;
    }
    void prepare() {
      if (pos()) p->prepare();
      propagate();
    }
    void rotate() {
      np q = p, c;
      if (pos() == 1) {
        c = l;
        l = p;
        p->r = c;
      } else {
        c = r;
        r = p;
        p->l = c;
      }
      if (c) c->p = p;
      p = p->p;
      q->p = this;
      if (p && p->l == q) p->l = this;
      if (p && p->r == q) p->r = this;
      q->update();
    }
    void splay() {
      prepare();
      while (pos()) {
        int first = pos(), second = p->pos();
        if (second && first == second) p->rotate();
        if (second && first != second) rotate();
        rotate();
      }
      update();
    }
    void expose() {
      for (np first = this; first; first = first->p) first->splay();
      for (np first = this; first->p; first = first->p) {
        first->p->r = first;
        first->p->update();
      }
      splay();
    }
    void evert() {
      expose();
      if (l) {
        l->reverse();
        l = 0;
        update();
      }
    }
    void link(np first) {
      evert();
      p = first;
    }
    template <class F, class... Args>
    np find(F f, Args&&... args) {
      if (!(x.*f)(forward<Args>(args)...)) return 0;
      propagate();
      x.single();
      np first = 0;
      if (l) first = l->find(f, forward<Args>(args)...);
      if (first) return first;
      if ((x.*f)(forward<Args>(args)...)) {
        splay();
        return this;
      }
      return r->find(f, forward<Args>(args)...);
    }
    void cutchild() {
      expose();
      r = 0;
      update();
    }
    void cutpar() {
      expose();
      assert(l);
      l->p = 0;
      l = 0;
      update();
    }
  } * x;
  linkcut(int n) { x = new Node[n]; }
  ~linkcut() { delete[] x; }
  using np = typename Node::np;
  int lca(int aa, int bb) {
    np first = x + aa, second = x + bb;
    first->expose();
    second->expose();
    if (!first->p) return -1;
    np d = first;
    while (first->p != second) {
      if (first->pos() == 0) d = first->p;
      first = first->p;
    }
    if (first == second->l)
      return d - x;
    else
      return second - x;
  }
  void link(int first, int second) { x[first].link(x + second); }
  void cutpar(int first) { x[first].cutpar(); }
  void expose(int first) { x[first].expose(); }
  void expose_path(int first, int second) {
    x[first].evert();
    x[second].cutchild();
  }
  N& operator[](int i) { return x[i].x; }
  template <class F, class... Args>
  int find(int first, F f, Args&&... args) {
    np res = x[first].find(f, forward<Args>(args)...);
    if (res)
      return res - x;
    else
      return -1;
  }
};
struct N {
  int v, s;
  void init(int first) {
    v = first;
    single();
  }
  void reverse() {}
  void push(N&) {}
  void clear() {}
  void single() { s = v; }
  void updatel(const N& x) { s += x.s; }
  void updater(const N& x) { s += x.s; }
  bool find() { return s; }
  void add(int x) {
    v += x;
    s += x;
  }
};
const int nmax = 250010;
vi g[nmax];
vc<pi> e2;
void dfs(int v, int p) {
  for (auto to : g[v])
    if (to != p) dfs(to, v);
  if (p != -1) e2.emplace_back(v, p);
}
signed main() {
  cin.tie(0);
  ios::sync_with_stdio(0);
  cout << fixed << setprecision(20);
  int n;
  cin >> n;
  linkcut<N> lc(n * 2 - 1);
  for (int i = int(0); i < int(n); i++) lc[i].init(0);
  vc<pi> e1;
  for (int i = int(0); i < int(n - 1); i++) {
    int first, second;
    cin >> first >> second;
    first--;
    second--;
    e1.emplace_back(first, second);
    lc[n + i].init(1);
    lc.link(first, n + i);
    lc.link(second, n + i);
  }
  for (int i = int(0); i < int(n - 1); i++) {
    int first, second;
    cin >> first >> second;
    first--;
    second--;
    g[first].push_back(second);
    g[second].push_back(first);
  }
  dfs(0, -1);
  print(n - 1);
  for (auto e : e2) {
    int c, d;
    tie(c, d) = e;
    lc.expose_path(c, d);
    int x = lc.find(d, &N::find);
    assert(x != -1);
    int first, second;
    tie(first, second) = e1[x - n];
    cout << first + 1 << " " << second + 1 << " " << c + 1 << " " << d + 1
         << "\n";
    lc[x].add(-1);
  }
}