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:
//In the Name of God
//Ya Ali

#include <bits/stdc++.h>

#define pii pair<int, int> 

#define err(A) cout << #A << " = " << (A) << endl

using namespace std;

const int maxn = 2048;

int n, m;

vector<int> g[maxn];
int d[maxn];

int st[maxn], ft[maxn], T;
int par[maxn];
int dis[maxn][maxn];

bool rev[maxn * 2];
int s[maxn * 2], t[maxn * 2];

int vis[maxn][maxn];

int M;
int q[maxn * maxn * 2], pt;
int l[maxn * 2], r[maxn * 2];

vector<pii> p[maxn];

bool mark[maxn];
bool kild[maxn * 2];

int ans;

void dfs(int v)
{
  st[v] = T ++;
  for(int u: g[v])
    if (u != par[v])
      par[u] = v, dfs(u);
  ft[v] = T ++;
}

int get_dis(int v, int u)
{
  if (~dis[v][u])
    return dis[v][u];
  if (v == u)
    return dis[v][u] = 0;
  if (v == 0)
    return dis[v][u] = get_dis(v, par[u]) + 1;
  else if (u == 0)
    return dis[v][u] = get_dis(par[v], u) + 1;
  return dis[v][u] = min(get_dis(v, par[u]), get_dis(par[v], u)) + 1;
}

void visit(int v, int u)
{
  if (v > u)
    swap(v, u);
  if (vis[v][u] < 2)
    ++ vis[v][u], ans ++;
}

int get_head(int id, int i, int v)
{
  if (r[id] > i + 1 and q[i + 1] == v)
    return q[r[id] - 1];
  else
    return q[l[id]];
}

void add_chain(int id, int x, int y, bool check = false)
{
  if (x == y)
    return;
  s[id] = x, t[id] = y;
  if (st[x] > st[y])
    swap(x, y);

  l[id] = pt;
  for(; ft[x] < ft[y]; x = par[x])
    q[pt ++] = x;
  q[pt ++] = x;
  
  r[id] = pt;
  for(; st[y] > st[x]; y = par[y])
    q[pt ++] = y;
  reverse(q + r[id], q + pt);
  r[id] = pt;

  if (q[l[id]] != s[id])
    reverse(q + l[id], q + r[id]);

  for (int i = l[id]; i < r[id]; i ++)
    p[q[i]].push_back({id, i});

  if (check)
    for (int i = l[id]; i + 1 < r[id]; i ++)
      visit(q[i], q[i + 1]);
}

void set_dir(int id, int v, int u)
{
  if (rev[id])
    swap(v, u);
  if (get_dis(s[id], v) + 1 + get_dis(u, t[id]) != get_dis(s[id], t[id]))
    rev[id] ^= true;
}

bool goes(int id, int i, int v)
{
  if (i + 1 < r[id] and q[i + 1] == v)
    return true;
  if (i - 1 >= l[id] and q[i - 1] == v)
    return true;
  return false;
}

void solve()
{  
  int v = -1, u;
  for (int i = 0; i < n; i ++)
    if (!mark[i] and d[i] == 1)
      v = i;
  if (v == -1)
    return;
  
  for (int o: g[v])
    if (!mark[o])
      u = o;

  mark[v] = true;
  d[u] --;

  int a = -1, b = -1, ai, bi;
  for (pii o: p[v])
    if (!kild[o.first] and goes(o.first, o.second, u))
      if (~a)
	b = o.first, bi = o.second;
      else
	a = o.first, ai = o.second;
  
  if (b == -1)
    {
      solve();
      return;
    }

  set_dir(a, v, u);
  set_dir(b, u, v);
  
  int that = M;
  add_chain(M ++, get_head(b, bi, u), get_head(a, ai, u));
  
  kild[a] = kild[b] = true;

  solve();
  
  rev[a] ^= rev[that];
  rev[b] ^= rev[that];
}

int main()
{
  ios::sync_with_stdio(0); cin.tie(0);

  cin >> n >> m;

  for (int i = 0; i < n - 1; i ++)
    {
      int v, u;
      cin >> v >> u;
      v --, u --;
      g[v].push_back(u);
      g[u].push_back(v);
      d[v] ++, d[u] ++;
    }

  dfs(0);
  memset(dis, -1, sizeof dis);

  for (int i = 0; i < m; i ++)
    {
      int v, u;
      cin >> v >> u;
      v --, u --;
      add_chain(M ++, v, u, true);
    }
  
  solve();

  cout << ans << "\n";
  
  for (int i = 0; i < m; i ++)
    if (rev[i])
      cout << t[i] + 1 << " " << s[i] + 1 << "\n";
    else
      cout << s[i] + 1 << " " << t[i] + 1 << "\n";
  
  return 0;
}