Problem: Takahashi loves walking on a tree. The tree where Takahashi walks has N vertices numbered 1 through N. The i-th of the N-1 edges connects Vertex a_i and Vertex b_i.

Takahashi has scheduled M walks. The i-th walk is done as follows:

* The walk involves two vertices u_i and v_i that are fixed beforehand.
* Takahashi will walk from u_i to v_i or from v_i to u_i along the shortest path.



The happiness gained from the i-th walk is defined as follows:

* The happiness gained is the number of the edges traversed during the i-th walk that satisfies one of the following conditions:
* In the previous walks, the edge has never been traversed.
* In the previous walks, the edge has only been traversed in the direction opposite to the direction taken in the i-th walk.



Takahashi would like to decide the direction of each walk so that the total happiness gained from the M walks is maximized. Find the maximum total happiness that can be gained, and one specific way to choose the directions of the walks that maximizes the total happiness.

Constraints

* 1 ≤ N,M ≤ 2000
* 1 ≤ a_i , b_i ≤ N
* 1 ≤ u_i , v_i ≤ N
* a_i \neq b_i
* u_i \neq v_i
* The graph given as input is a tree.

Input

Input is given from Standard Input in the following format:


N M
a_1 b_1
:
a_{N-1} b_{N-1}
u_1 v_1
:
u_M v_M


Output

Print the maximum total happiness T that can be gained, and one specific way to choose the directions of the walks that maximizes the total happiness, in the following format:


T
u^'_1 v^'_1
:
u^'_M v^'_M


where (u^'_i,v^'_i) is either (u_i,v_i) or (v_i,u_i), which means that the i-th walk is from vertex u^'_i to v^'_i.

Examples

Input

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


Output

6
2 3
3 4
4 2


Input

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


Output

6
2 4
3 5
5 1


Input

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


Output

9
2 4
6 3
5 6
4 5

Solution (in CPP):

Solution:
/**
 *    author:  tourist
 *    created: 22.11.2019 20:40:28       
**/
#include <bits/stdc++.h>

using namespace std;

class dsu {
 public:
  vector<int> p;
  int n;

  dsu(int _n) : n(_n) {
    p.resize(n);
    iota(p.begin(), p.end(), 0);
  }

  inline int get(int x) {
    return (x == p[x] ? x : (p[x] = get(p[x])));
  }

  inline bool unite(int x, int y) {
    x = get(x);
    y = get(y);
    if (x != y) {
      p[x] = y;
      return true;
    }
    return false;
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  vector<vector<pair<int, int>>> g(n);
  for (int i = 0; i < n - 1; i++) {
    int x, y;
    cin >> x >> y;
    --x; --y;
    g[x].emplace_back(y, i);
    g[y].emplace_back(x, i);
  }
  vector<int> from(m), to(m);
  for (int i = 0; i < m; i++) {
    cin >> from[i] >> to[i];
    --from[i]; --to[i];
  }
  vector<vector<int>> uses(m, vector<int>(n - 1, 0));
  vector<vector<int>> at(n - 1);
  vector<int> any_que;
  vector<int> any_pe;
  for (int i = 0; i < m; i++) {
    vector<int> pr(n, -1);
    vector<int> pe(n, -1);
    vector<int> que(1, from[i]);
    pr[from[i]] = -2;
    for (int b = 0; b < (int) que.size(); b++) {
      for (auto& p : g[que[b]]) {
        int u = p.first;
        if (pr[u] == -1) {
          que.push_back(u);
          pr[u] = que[b];
          pe[u] = p.second;
        }
      }
    }
    any_que = que;
    any_pe = pe;
    int v = to[i];
    while (v != from[i]) {
      int me = i + m * (v < pr[v]);
      at[pe[v]].push_back(me);
      v = pr[v];
    }
  }
  int ans = 0;
  for (int i = 0; i < n - 1; i++) {
    ans += min((int) at[i].size(), 2);
  }
  vector<int> skip(m, 0);
  dsu d(2 * m);
  for (int it = n - 1; it > 0; it--) {
    int e = any_pe[any_que[it]];
    set<int> who;
    for (int i : at[e]) {
      who.insert(d.get(i) % m);
    }
    if (who.size() < at[e].size() || who.size() < 2) {
      continue;
    }
    int x = d.get(*at[e].begin());
    int y = d.get(*next(at[e].begin()));
    d.unite(x, (y + m) % (2 * m));
    d.unite((x + m) % (2 * m), y);
  }
  for (int i = 0; i < m; i++) {
    assert(d.get(i) != d.get(i + m));
  }
  cout << ans << '\n';
  for (int i = 0; i < m; i++) {
    if (i / m != d.get(i) / m) {
      swap(from[i], to[i]);
    }
    cout << from[i] + 1 << " " << to[i] + 1 << '\n';
  }
  return 0;
}