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;
typedef long long ll;

const int MaxN = 2005;

int n, m, dir[MaxN], u[MaxN], v[MaxN], w[MaxN], par[MaxN], dep[MaxN], fe[MaxN];

vector<int> edge[MaxN], pass[MaxN];

void dfs(int x, int fa) {
  for (int y : edge[x])
    if (y != fa) {
      par[y] = x; dep[y] = dep[x] + 1;
      dfs(y, x);
    }
}

bool f[MaxN][2], vis[MaxN];
void refresh(int i, int o) {
  for (int x = u[i]; x != w[i]; --fe[x], f[x][o ^ 0] = true, x = par[x]);
  for (int x = v[i]; x != w[i]; --fe[x], f[x][o ^ 1] = true, x = par[x]);
}

bool decrease() {
  for (int i = 1; i <= n; i++) {
    if (fe[i] == 1 && (!f[i][0] || !f[i][1])) {
      bool c1 = f[i][0], c2 = 1;
      for (auto x : pass[i]) {
        if (!vis[x]) {
          int p = u[x];
          while (p != w[x]) {
            if (p == i)
              c2 = false;
            p = par[p];
          }
          dir[x] = (c1 ^ c2); vis[x] = true; refresh(x, c1 ^ c2); 
          break;
        }
      }     
      return true;
    }
  }
  return false;
}

int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1, u, v; i < n; i++) {
    scanf("%d%d", &u, &v);
    edge[u].push_back(v);
    edge[v].push_back(u);
  }
  dfs(1, 0);
  for (int i = 1; i <= m; i++) {
    scanf("%d%d", u + i, v + i);
    for (int x = u[i], y = v[i]; x != y; ) {
      if (dep[x] < dep[y]) swap(x, y);
      ++fe[x]; pass[x].push_back(i); x = par[x]; 
      w[i] = x;
    }
  }
  int ans = 0;
  for (int i = 1; i <= n; i++) ans += min(fe[i], 2);
  printf("%d\n", ans);
  for (int i = 1; i <= n; i++) if (fe[i] < 2) fe[i] = 0;
  for (int i = 1; i <= m; i++) {
    if (!vis[i]) {
      vis[i] = true;
      for (refresh(i, 0); decrease(); ); 
    }
  }
  
  for (int i = 1; i <= m; i++) {
    int x = u[i], y = v[i];
    if (dir[i])
      swap(x, y);
    printf("%d %d\n", x, y); 
  }
  return 0;
}