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 pair<int, int> pii;

const int MAX_N = 2333;

int N, M, pa[MAX_N], deg[MAX_N];
bool done[MAX_N];
vector<int> edge[MAX_N];

void dfs(int x, int y, int pa[]) {
    pa[x] = y;
    for (int i : edge[x]) {
        if (i == y) continue;
        pa[i] = x;
        dfs(i, x, pa);
    }
}

void solve(pii walks[], int n) {
    int leaf = 0;
    for (int i = 1; i <= N; i++) {
        if (deg[i] == 0 && !done[i]) {
            done[leaf = i] = true;
            break;
        }
    }
    assert(leaf);
    done[leaf] = true;
    deg[pa[leaf]]--;
    pii trans[MAX_N];
    int m = 0, src[MAX_N];
    bool cut[MAX_N];
    fill_n(cut + 1, n, false);
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (walks[i].first == walks[i].second) continue;
        if (walks[i].first == leaf || walks[i].second == leaf) {
            cnt++;
            if (walks[i].second == leaf) swap(walks[i].first, walks[i].second);
        }
    }
    vector<int> attached;
    if (cnt >= 2) {
        for (int i = 1; i <= n && attached.size() < 2; i++) {
            if (walks[i].first == walks[i].second) continue;
            if (walks[i].first == leaf) {
                attached.push_back(i);
            }
        }
        trans[m = 1] = make_pair(walks[attached[0]].second, walks[attached[1]].second);
    }
    for (int i = 1; i <= n; i++) {
        if (walks[i].first == walks[i].second) continue;
        if (count(attached.begin(), attached.end(), i)) continue;
        trans[++m] = walks[i];
        src[m] = i;
        if (trans[m].first == leaf) {
            cut[i] = true;
            trans[m].first = pa[leaf];
        }
    }
    if (m == 0) return;
    solve(trans, m);
    if (!attached.empty()) {
        if (trans[1].first == walks[attached[1]].second)
            swap(attached[0], attached[1]);
        walks[attached[0]] = make_pair(trans[1].first, leaf);
        walks[attached[1]] = make_pair(leaf, trans[1].second);
    }
    for (int i = attached.empty() ? 1 : 2; i <= m; i++) {
        walks[src[i]] = trans[i];
    }
    for (int i = 1; i <= n; i++) {
        if (cut[i]) {
            if (walks[i].first == pa[leaf]) walks[i].first = leaf;
            else if (walks[i].second == pa[leaf]) walks[i].second = leaf;
        }
    }
}

int main() {
    scanf("%d%d", &N, &M);
    for (int i = 1; i < N; i++) {
        int a, b; scanf("%d%d", &a, &b);
        edge[a].push_back(b); edge[b].push_back(a);
    }
    dfs(1, 0, pa);
    for (int i = 1; i <= N; i++) deg[i] = edge[i].size() - (i != 1);
    pii walks[MAX_N];
    for (int i = 1; i <= M; i++) {
        scanf("%d%d", &walks[i].first, &walks[i].second);
    }
    solve(walks, M);
    vector<pii> cov;
    for (int i = 1; i <= M; i++) {
        int tpa[MAX_N];
        dfs(walks[i].first, 0, tpa);
        for (int j = walks[i].second; j != walks[i].first; j = tpa[j]) {
            cov.emplace_back(tpa[j], j);
        }
    }
    sort(cov.begin(), cov.end());
    cov.erase(unique(cov.begin(), cov.end()), cov.end());
    printf("%zu\n", cov.size());
    for (int i = 1; i <= M; i++) {
        printf("%d %d\n", walks[i].first, walks[i].second);
    }
}