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;

const int N = 2024; // No Corona those days, I hope

vector<int> g[N];

int pv[N];
int dep[N];

void dfs(int v, int p = -1) {
  pv[v] = p;
  for (int to : g[v]) {
    if (to != p) {
      dep[to] = dep[v] + 1;
      dfs(to, v);
    }
  }
}

int have[N][N];
int walk[N][N];

void del(int a, int b) {
  --have[a][b];
  --have[b][a];
}

void add(int a, int b) {
  ++have[a][b];
  ++have[b][a];
}

void dir(int a, int b) {
  del(a, b);
  ++walk[a][b];
}

bool mark[N];
int deg[N];
int n, m;

void Solve() {
  int leaf = -1;
  for (int i = 0; i < n; i++) {
    if (!mark[i] && deg[i] == 1) {
      leaf = i;
      break;
    }
  }
  if (leaf == -1) {
    for (int i = 0; i < n; i++) {
      if (!mark[i]) {
        mark[i] = true;
        while (have[i][i]) {
          dir(i, i);
        }
      }
    }
    return;
  }
  mark[leaf] = true;
  int other = -1;
  for (int x : g[leaf]) {
    if (!mark[x]) {
      other = x;
      break;
    }
  }
  assert(other != -1);
  --deg[other];
  int a = -1, b = -1;
  vector<int> vec;
  for (int i = 0; i < n; i++) {
    if (mark[i]) continue;
    if (have[i][leaf]) {
      a = (a == -1 ? i : a);
      b = i;
      vec.emplace_back(i);
    }
  }
  if (a == b && have[a][leaf] == 1) {
    a = -1;
  }
  while (have[leaf][leaf]) {
    dir(leaf, leaf);
  }
  if (a != -1 && b != -1) {
    del(a, leaf);
    del(b, leaf);
    add(a, b);
  } else if (b != -1) {
    del(b, leaf);
    add(b, other);
  }
  vector<int> done;
  for (int x : vec) {
    while (have[leaf][x]) {
      del(leaf, x);
      add(other, x);
      done.push_back(x);
    }
  }
  Solve();
  ++deg[other];
  for (int x : done) {
    if (walk[other][x]) {
      --walk[other][x];
      ++walk[leaf][x];
    } else if (walk[x][other]) {
      --walk[x][other];
      ++walk[x][leaf];
    } else {
      throw;
    }
  }
  if (a != -1 && b != -1) {
    if (walk[a][b]) {
      --walk[a][b];
      ++walk[a][leaf];
      ++walk[leaf][b];
    } else if (walk[b][a]) {
      --walk[b][a];
      ++walk[b][leaf];
      ++walk[leaf][a];
    } else {
      throw;
    }
  } else if (b != -1) {
    if (walk[b][other]) {
      --walk[b][other];
      ++walk[b][leaf];
    } else if (walk[other][b]) {
      --walk[other][b];
      ++walk[leaf][b];
    } else {
      throw;
    }
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> m;
  for (int i = 0; i < n - 1; ++i) {
    int x, y;
    cin >> x >> y;
    --x; --y;
    g[x].push_back(y);
    g[y].push_back(x);
    ++deg[x];
    ++deg[y];
  }
  dfs(0);
  vector<int> cnt(n);
  vector<pair<int, int>> sched;
  for (int i = 0; i < m; i++) {
    int x, y;
    cin >> x >> y;
    --x; --y;
    sched.emplace_back(x, y);
    add(x, y);
    while (x != y) {
      if (dep[x] < dep[y]) {
        swap(x, y);
      }
      ++cnt[x];
      x = pv[x];
    }
  }
  Solve();
  int ans = 0;
  for (int i = 0; i < n; i++) {
    ans += min(2, cnt[i]);
  }
  cout << ans << '\n';
  for (int i = 0; i < m; i++) {
    int x = sched[i].first;
    int y = sched[i].second;
    if (walk[x][y] > 0) {
      --walk[x][y];
      cout << x + 1 << " " << y + 1 << '\n';
    } else {
      --walk[y][x];
      cout << y + 1 << " " << x + 1 << '\n';
    }
  }
  return 0; // :)
}