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 <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cmath>
#include <iomanip>
#include <cassert>
#include <bitset>
using namespace std;

typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end())
#define index(xs, x) (int)(lower_bound(all(xs), x) - xs.begin())
#define _1 first
#define _2 second
#define pb push_back
#define INF 1145141919
#define MOD 1000000007

int N, M;
vector<int> G[2000];
int U[2000], R[2000];
int MU[2000], MV[2000];
int ex[2000];
set<int> C[2000];
vector<int> leftE[2000], rightE[2000];
bool up[2000], down[2000];
bool dead[2000];
bool dir[2000];

void dfs(int x, int p, int r) {
  U[x] = p, R[x] = r;
  for (int t : G[x]) if (t != p) dfs(t, x, r+1);
}
void go(int id, bool d) {
  assert(!dead[id]);
  dead[id] = true;
  dir[id] = d;
  //cout<<"id="<<id<<": dir="<<d<<"\n";
  //if (dir[id]) cout << MU[id]+1 << "->" << MV[id]+1 <<"\n";
  //else cout << MV[id]+1 << "->" << MU[id]+1 <<"\n";

  for (int e : leftE[id]) {
    if (d) up[e] = true;
    else down[e] = true;
  }
  for (int e : rightE[id]) {
    if (d) down[e] = true;
    else up[e] = true;
  }
  rep(i, N) C[i].erase(id), C[i].erase(id+M);
}

signed main() {
  ios::sync_with_stdio(false); cin.tie(0);
  cin >> N >> M;
  rep(i, N-1) {
    int a, b;
    cin >> a >> b;
    a--, b--;
    G[a].pb(b);
    G[b].pb(a);
  }
  dfs(0, -1, 0);
  rep(i, M) {
    int u, v;
    cin >> u >> v;
    u--, v--;
    if (R[u] < R[v]) swap(u, v);
    MU[i] = u, MV[i] = v;
    while (R[u] != R[v]) leftE[i].pb(u), u = U[u];
    while (u != v) leftE[i].pb(u), u = U[u], rightE[i].pb(v), v = U[v];
    for (int x : leftE[i]) C[x].insert(i);
    for (int x : rightE[i]) C[x].insert(i+M);
  }
  rep(i, N) ex[i] = min((int)C[i].size(), 2);
  int s = 0;
  rep(i, N) s += ex[i];
  cout << s << "\n";

  int ctr = 0;
  while (ctr < M) {
    bool none = true;
    rep(i, N) if (ex[i]==2 && (up[i]^down[i]) && C[i].size() == 1) {
      int id = *C[i].begin();
      bool is_up = (!up[i]) ^ (id >= M);
      if (id >= M) id -= M;
      ctr++;
      none = false;
      go(id, is_up);
      break;
    }
    if (none) {
      int id = 0;
      while (id<M && dead[id]) id++;
      assert(id != M);
      //cout<<"none="<<id<<"\n";
      go(id, true);
      ctr++;
    }
  }
  rep(i, N) assert(ex[i] == 0+up[i]+down[i]);
  rep(i, M) {
    if (dir[i]) cout << MU[i]+1 << " " << MV[i]+1 <<"\n";
    else cout << MV[i]+1 << " " << MU[i]+1 <<"\n";
  }
  return 0;
}