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;
struct segment_change {
  static const int SENTINEL = numeric_limits<int>::min();
  int to_set;
  segment_change(int _to_set = SENTINEL) : to_set(_to_set) {}
  bool has_set() const { return to_set != SENTINEL; }
  void reset() { to_set = SENTINEL; }
  bool has_change() const { return has_set(); }
  segment_change combine(const segment_change &other) const {
    return other.has_set() ? other : *this;
  }
};
struct segment {
  int first;
  segment(int _first = -1) : first(_first) {}
  void apply(int, const segment_change &change) {
    if (change.has_set()) first = change.to_set;
  }
  void join(const segment &other) {
    if (first < 0) first = other.first;
  }
  void join(const segment &a, const segment &b) {
    *this = a;
    join(b);
  }
};
pair<int, int> right_half[32];
struct seg_tree {
  int tree_n = 0;
  vector<segment> tree;
  vector<segment_change> changes;
  seg_tree(int n = -1) {
    if (n >= 0) init(n);
  }
  void init(int n) {
    tree_n = 1;
    while (tree_n < n) tree_n *= 2;
    tree.assign(2 * tree_n, segment());
    changes.assign(tree_n, segment_change());
  }
  void build(const vector<segment> &initial) {
    int n = initial.size();
    init(n);
    assert(n <= tree_n);
    for (int i = 0; i < n; i++) tree[tree_n + i] = initial[i];
    for (int position = tree_n - 1; position > 0; position--)
      tree[position].join(tree[2 * position], tree[2 * position + 1]);
  }
  void push_down(int position, int length) {
    if (!changes[position].has_change()) return;
    if (2 * position < tree_n) {
      changes[2 * position] = changes[2 * position].combine(changes[position]);
      changes[2 * position + 1] =
          changes[2 * position + 1].combine(changes[position]);
    }
    tree[2 * position].apply(length / 2, changes[position]);
    tree[2 * position + 1].apply(length / 2, changes[position]);
    changes[position].reset();
  }
  void push_all(int a, int b) {
    assert(0 <= a && a < b && b <= tree_n);
    a += tree_n;
    b += tree_n - 1;
    for (int up = 31 - __builtin_clz(tree_n); up > 0; up--) {
      int x = a >> up, y = b >> up;
      push_down(x, 1 << up);
      if (x != y) push_down(y, 1 << up);
    }
  }
  void join_and_apply(int position, int length) {
    tree[position].join(tree[2 * position], tree[2 * position + 1]);
    tree[position].apply(length, changes[position]);
  }
  void join_all(int a, int b) {
    assert(0 <= a && a < b && b <= tree_n);
    a += tree_n;
    b += tree_n - 1;
    int length = 1;
    while (a > 1) {
      a /= 2;
      b /= 2;
      length *= 2;
      join_and_apply(a, length);
      if (a != b) join_and_apply(b, length);
    }
  }
  template <typename T_range_op>
  void process_range(int a, int b, bool needs_join, T_range_op &&range_op) {
    if (a == b) return;
    push_all(a, b);
    int original_a = a, original_b = b;
    int length = 1, r_size = 0;
    for (a += tree_n, b += tree_n; a < b; a /= 2, b /= 2, length *= 2) {
      if (a & 1) range_op(a++, length);
      if (b & 1) right_half[r_size++] = {--b, length};
    }
    for (int i = r_size - 1; i >= 0; i--)
      range_op(right_half[i].first, right_half[i].second);
    if (needs_join) join_all(original_a, original_b);
  }
  segment query(int a, int b) {
    assert(0 <= a && a <= b && b <= tree_n);
    segment answer;
    process_range(a, b, false,
                  [&](int position, int) { answer.join(tree[position]); });
    return answer;
  }
  void update(int a, int b, const segment_change &change) {
    assert(0 <= a && a <= b && b <= tree_n);
    process_range(a, b, true, [&](int position, int length) {
      tree[position].apply(length, change);
      if (position < tree_n)
        changes[position] = changes[position].combine(change);
    });
  }
};
static segment v_half[32];
struct ordered_path_heavy_light {
  int n = 0;
  bool vertex_mode;
  vector<vector<int>> adj;
  vector<int> parent, depth, subtree_size;
  vector<int> chain_root, chain_size;
  vector<seg_tree> chain_up_tree, chain_down_tree;
  ordered_path_heavy_light() {}
  ordered_path_heavy_light(int _n, bool _vertex_mode) {
    init(_n, _vertex_mode);
  }
  void init(int _n, bool _vertex_mode) {
    n = _n;
    vertex_mode = _vertex_mode;
    adj.assign(n, {});
    parent.resize(n);
    depth.resize(n);
    subtree_size.resize(n);
    chain_root.resize(n);
    chain_size.assign(n, 0);
    chain_up_tree.assign(n, {});
    chain_down_tree.assign(n, {});
  }
  void add_edge(int a, int b) {
    adj[a].push_back(b);
    adj[b].push_back(a);
  }
  void dfs(int node, int par) {
    parent[node] = par;
    depth[node] = par < 0 ? 0 : depth[par] + 1;
    subtree_size[node] = 1;
    if (par >= 0)
      adj[node].erase(find(adj[node].begin(), adj[node].end(), par));
    for (int &child : adj[node]) {
      dfs(child, node);
      subtree_size[node] += subtree_size[child];
    }
    sort(adj[node].begin(), adj[node].end(),
         [&](int a, int b) { return subtree_size[a] > subtree_size[b]; });
  }
  void chain_dfs(int node, bool heavy) {
    chain_root[node] = heavy ? chain_root[parent[node]] : node;
    chain_size[chain_root[node]]++;
    bool heavy_child = true;
    for (int child : adj[node]) {
      chain_dfs(child, heavy_child);
      heavy_child = false;
    }
  }
  void build(const segment &initial) {
    parent.assign(n, -1);
    for (int i = 0; i < n; i++)
      if (parent[i] < 0) {
        dfs(i, -1);
        chain_dfs(i, false);
      }
    for (int i = 0; i < n; i++)
      if (chain_root[i] == i) {
        chain_up_tree[i].init(chain_size[i]);
        chain_down_tree[i].init(chain_size[i]);
        vector<segment> initial_segs(chain_size[i], initial);
        chain_up_tree[i].build(initial_segs);
        chain_down_tree[i].build(initial_segs);
      }
  }
  segment _query_up_tree(int root, int start, int end) {
    int size = chain_size[root];
    return chain_up_tree[root].query(size - end, size - start);
  }
  void _update_up_tree(int root, int start, int end,
                       const segment_change &change) {
    int size = chain_size[root];
    chain_up_tree[root].update(size - end, size - start, change);
  }
  void _update_both_trees(int root, int start, int end,
                          const segment_change &change) {
    _update_up_tree(root, start, end, change);
    chain_down_tree[root].update(start, end, change);
  }
  segment query_path(int u, int v) {
    segment u_half;
    int v_size = 0;
    while (chain_root[u] != chain_root[v]) {
      bool pull_u = depth[chain_root[u]] > depth[chain_root[v]];
      int pull_node = pull_u ? u : v;
      int root = chain_root[pull_node];
      int end = depth[pull_node] - depth[root] + 1;
      if (pull_u) {
        u_half.join(_query_up_tree(root, 0, end));
        u = parent[root];
      } else {
        v_half[v_size++] = chain_down_tree[root].query(0, end);
        v = parent[root];
      }
    }
    bool pull_u = depth[u] > depth[v];
    int pull_node = pull_u ? u : v;
    int ancestor = pull_u ? v : u;
    int root = chain_root[pull_node];
    int start = depth[ancestor] - depth[root] + (vertex_mode ? 0 : 1);
    int end = depth[pull_node] - depth[root] + 1;
    if (pull_u)
      u_half.join(_query_up_tree(root, start, end));
    else
      v_half[v_size++] = chain_down_tree[root].query(start, end);
    for (int i = v_size - 1; i >= 0; i--) u_half.join(v_half[i]);
    return u_half;
  }
  void update_path(int u, int v, const segment_change &change) {
    while (chain_root[u] != chain_root[v]) {
      if (depth[chain_root[u]] > depth[chain_root[v]]) swap(u, v);
      int root = chain_root[v];
      _update_both_trees(root, 0, depth[v] - depth[root] + 1, change);
      v = parent[root];
    }
    if (depth[u] > depth[v]) swap(u, v);
    int root = chain_root[v];
    _update_both_trees(root, depth[u] - depth[root] + (vertex_mode ? 0 : 1),
                       depth[v] - depth[root] + 1, change);
  }
};
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int N;
  cin >> N;
  ordered_path_heavy_light HLD(N, false);
  vector<pair<int, int>> T1(N - 1);
  for (int i = 0; i < N - 1; i++) {
    int a, b;
    cin >> a >> b;
    a--;
    b--;
    HLD.add_edge(a, b);
    T1[i] = {a, b};
  }
  HLD.build(segment());
  for (int e = 0; e < N - 1; e++)
    HLD.update_path(T1[e].first, T1[e].second, segment_change(e));
  vector<vector<int>> adj(N);
  vector<int> degree(N, 0);
  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);
    degree[a]++;
    degree[b]++;
  }
  queue<int> leaves;
  for (int i = 0; i < N; i++)
    if (degree[i] == 1) leaves.push(i);
  cout << N - 1 << '\n';
  while (!leaves.empty()) {
    int leaf = leaves.front();
    leaves.pop();
    if (degree[leaf] == 0) break;
    int parent = -1;
    for (int neighbor : adj[leaf])
      if (degree[neighbor] != 0) parent = neighbor;
    assert(parent >= 0);
    int first_edge = HLD.query_path(leaf, parent).first;
    assert(first_edge >= 0);
    int x = T1[first_edge].first, y = T1[first_edge].second;
    HLD.update_path(x, y, segment_change(-1));
    degree[leaf]--;
    degree[parent]--;
    if (degree[parent] == 1) leaves.push(parent);
    cout << x + 1 << ' ' << y + 1 << ' ' << leaf + 1 << ' ' << parent + 1
         << '\n';
  }
}