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>

#define LOG(FMT...) fprintf(stderr, FMT)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;

// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

template <class T>
istream& operator>>(istream& is, vector<T>& v) {
  for (T& x : v)
    is >> x;
  return is;
}

ostream& operator<<(ostream& os, const pair<char, int>& unit) {
  return os << unit.first << "^" << unit.second;
}

template <class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
  if (!v.empty()) {
    os << v.front();
    for (int i = 1; i < v.size(); ++i)
      os << ' ' << v[i];
  }
  return os;
}

const int N = 2010;

int n, m;
int pu[N][2], ch[N * 2][2], prt[N], dep[N], c[N];
bool vis[N], tag[N * 2];
vi g[N];
vector<pair<int, int>> pth[N];

void dfs(int u) {
  vis[u] = true;
  for (int v : g[u])
    if (!vis[v]) {
      dep[v] = dep[u] + 1;
      prt[v] = u;
      dfs(v);
    }
}

int main() {
#ifdef LBT
  freopen("test.in", "r", stdin);
  int nol_cl = clock();
#endif
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  cin >> n >> m;
  for (int rep = 1; rep < n; ++rep) {
    int u, v;
    cin >> u >> v;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  dfs(1);
  int cnt = m;
  for (int i = 1; i <= m; ++i) {
    cin >> pu[i][0] >> pu[i][1];
    pth[pu[i][0]].emplace_back(pu[i][1], i);
    pth[pu[i][1]].emplace_back(pu[i][0], -i);
    int uu = pu[i][0], vv = pu[i][1];
    while (uu != vv) {
      if (dep[uu] > dep[vv]) {
        ++c[uu];
        uu = prt[uu];
      } else {
        ++c[vv];
        vv = prt[vv];
      }
    }
  }
  int ans = 0;
  for (int i = 1; i <= n; ++i)
    ans += min(c[i], 2);
  for (int rep = 1; rep < n; ++rep) {
    int u = 1;
    while (g[u].size() != 1) ++u;
    if (pth[u].size() >= 2) {
      int v1, i1, v2, i2;
      tie(v1, i1) = pth[u].back(); pth[u].pop_back();
      tie(v2, i2) = pth[u].back(); pth[u].pop_back();
      if ((i1 < 0) == (i2 < 0)) {
        tag[abs(i2)] ^= 1;
        find(pth[v2].begin(), pth[v2].end(), make_pair(u, -i2))->second = i2;
        i2 = -i2;
      }
      if (i1 > 0) {
        swap(i1, i2);
        swap(v1, v2);
      }
      ++cnt;
      ch[cnt][0] = -i1; ch[cnt][1] = i2;
      if (v1 != v2) {
        *find(pth[v1].begin(), pth[v1].end(), make_pair(u, -i1)) = make_pair(v2, cnt);
        *find(pth[v2].begin(), pth[v2].end(), make_pair(u, -i2)) = make_pair(v1, -cnt);
      } else {
        pth[v1].erase(find(pth[v1].begin(), pth[v1].end(), make_pair(u, -i1)));
        pth[v2].erase(find(pth[v2].begin(), pth[v2].end(), make_pair(u, -i2)));
      }
    }
    int adj = g[u].back();
    for (const auto& pr : pth[u]) {
      int v, i;
      tie(v, i) = pr;
      if (u == v) continue;
      if (adj != v) {
        pth[adj].emplace_back(v, i);
        find(pth[v].begin(), pth[v].end(), make_pair(u, -i))->first = adj;
      } else
        pth[v].erase(find(pth[v].begin(), pth[v].end(), make_pair(u, -i)));
    }
    g[u].clear();
    g[adj].erase(find(g[adj].begin(), g[adj].end(), u));
  }
  for (int i = cnt; i > m; --i) {
    for (int j = 0; j < 2; ++j)
      tag[ch[i][j]] ^= tag[i];
  }
  cout << ans << '\n';
  for (int i = 1; i <= m; ++i)
    cout << pu[i][tag[i]] << ' ' << pu[i][!tag[i]] << '\n';

#ifdef LBT
  LOG("Time: %dms\n", int ((clock()
      -nol_cl) / (double)CLOCKS_PER_SEC * 1000));
#endif
  return 0;
}