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:
#include <bits/stdc++.h>

using namespace std;

#define range(i, m, n) for(int i = m; i < n; i++)
#define husk(i, m, n) for(int i = m; i > n; i--)

int n, m;

int main() {
  cin >> n >> m;
  vector<vector<int>> g(n);
  vector<int> a(n - 1);
  vector<int> b(n - 1);
  range(i, 0, n - 1) {
    int u, v;
    cin >> u >> v;
    u--; v--;
    a[i] = u; b[i] = v;
    g[u].push_back(i);
    g[v].push_back(i);
  }
  vector<int> par(n);
  function<void(int, int)> dfs = [&] (int v, int p) {
    par[v] = p;
    int pp = (~p ? a[p] + b[p] - v : -1);
    for(int id : g[v]) {
      int u = a[id] + b[id] - v;
      if(u != pp) dfs(u, id);
    }
  };
  dfs(0, -1);
  vector<int> x(m), y(m);
  vector<set<int>> to(n);
  vector<vector<int>> path(m);
  range(i, 0, m) {
    int u, v;
    cin >> u >> v;
    u--; v--;
    x[i] = u; y[i] = v;
    vector<int> su, sv;
    while(~par[u]) {
      su.push_back(par[u]);
      int p = a[par[u]] + b[par[u]] - u;
      if(u > p) su.back() = ~su.back();
      u = p;
    }
    while(~par[v]) {
      sv.push_back(par[v]);
      int p = a[par[v]] + b[par[v]] - v;
      if(v > p) sv.back() = ~sv.back();
      v = p;
    }
    while(!su.empty() && !sv.empty() && su.back() == sv.back()) {
      su.pop_back(); sv.pop_back();
    }
    for(int id : su) {
      path[i].push_back(id);
    }
    for(int id : sv) {
      path[i].push_back(~id);
    }
    for(int id : path[i]) {
      if(id >= 0) to[id].insert(i);
      else to[~id].insert(~i);
    }
  }
  int res = 0;
  range(i, 0, n - 1) {
    res += min(2, (int) to[i].size());
  }
  cout << res << endl;
  vector<int> cur(n - 1);
  vector<bool> rev(m);
  range(i, 0, n - 1) if(to[i].size() == 1) cur[i] = 3;
  while(true) {
    int id = -1;
    range(i, 0, n - 1) {
      if(cur[i] == 3 || to[i].empty()) continue;
      if(id == -1 || to[i].size() < to[id].size()) id = i;
    }
    if(id == -1) break;
    int c = *to[id].begin();
    if(cur[id] == 1) c = ~c;
    int s = max(c, ~c);
    rev[s] = c < 0;
    for(int id : path[s]) {
      if((id < 0) ^ (c < 0)) cur[max(id, ~id)] |= 2;
      else cur[max(id, ~id)] |= 1;
      id = max(id, ~id);
      to[id].erase(s);
      to[id].erase(~s);
    }
  }
  range(i, 0, m) if(rev[i]) swap(x[i], y[i]);
  range(i, 0, m) {
    cout << x[i] + 1 << " " << y[i] + 1 << endl;
  }
  return 0;
}