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 pw(x) (1LL << (x))
#define db(x) cerr << #x << " = " << x << endl
#define db2(x, y) cerr << "(" << #x << ", " << #y << ") = (" << x << ", " << y << ")" << endl

using namespace std;
typedef long long ll;
typedef double dbl;
const int INF = 1.01e9;

pair<int, vector<pair<int, int>>> solve(vector<pair<int, int>> ed, vector<pair<int, int>> path) {
    int n = ed.size() + 1;
    int m = path.size();

    vector<vector<int>> e(n);
    for (int i = 0; i < n - 1; i++) {
        e[ed[i].first].push_back(i);
        e[ed[i].second].push_back(i);
    }

    vector<set<pair<int, int>>> paths(n - 1);
    vector<vector<int>> edges(m);
    for (int i = 0; i < m; i++) {
        function<bool(int, int)> dfs = [&](int v, int pr) {
            if (v == path[i].second) {
                return true;
            }
            for (int id : e[v]) {
                int to = ed[id].first ^ ed[id].second ^ v;
                if (to == pr) continue;
                if (dfs(to, v)) {
                    edges[i].push_back(id);
                    paths[id].insert({i, to == ed[id].first});
                    return true;
                }
            }
            return false;
        };
        dfs(path[i].first, -1);
    }
    auto opaths = paths;

    int need = 0;
    for (int i = 0; i < n - 1; i++) need += min((int)paths[i].size(), 2);

    vector<vector<int>> have(n - 1, vector<int>(2));

    vector<int> color(m, -1);
    function<void(int, int)> paint = [&](int p, int c) {
        if (color[p] != -1) {
            assert(color[p] == c);
            return;
        }
        color[p] = c;
        for (auto id : edges[p]) {
            auto it = paths[id].lower_bound(make_pair(p, -1));
            auto o = *it;
            have[id][o.second ^ c] = 1;
            paths[id].erase(it);
            if (paths[id].size() == 1 && !have[id][o.second ^ c ^ 1]) {
                paint(paths[id].begin()->first, paths[id].begin()->second ^ o.second ^ c ^ 1);
            }
        }
    };
    for (int i = 0; i < m; i++) {
        if (color[i] == -1) {
            paint(i, 0);
        }
    }

    int res = 0;
    for (int i = 0; i < n - 1; i++) {
        vector<char> chave(2);
        for (auto o : opaths[i]) {
            chave[o.second ^ color[o.first]] = 1;
        }
        res += chave[0];
        res += chave[1];
        assert(chave[0] == have[i][0]);
        assert(chave[1] == have[i][1]);
    }

    assert(res == need);
    for (int i = 0; i < m; i++) {
        if (color[i] == 1) {
            swap(path[i].first, path[i].second);
        }
    }
    return make_pair(res, path);
};

void stress() {
    for (int it = 246;; it++ ){
        cout << it << endl;
        srand(it);

        int n = rand() % 10 + 2;
        int m = rand() % (2 * n) + 1;
        vector<pair<int, int>> ed(n - 1), path(m);
        for (int i = 0; i < n - 1; i++) {
            ed[i] = {i + 1, rand() % (i + 1)};
        }
        for (int i = 0; i < m; i++) {
            while (path[i].first == path[i].second) {
                path[i].first = rand() % n;
                path[i].second = rand() % n;
            }
        }

        /*cout << n << " " << m << endl;
        for (auto o : ed) cout << o.first << " " << o.second << endl;
        for (auto o : path) cout << o.first << " " << o.second << endl;*/
        auto o = solve(ed, path);
        //cout << solve(ed, path).first << endl;
    }
}

int main() {
#ifdef HOME
    assert(freopen("in", "r", stdin));
#endif
    //stress();

    int n, m;
    while (scanf("%d%d", &n, &m) == 2) {
        vector<pair<int, int>> ed(n - 1);
        for (int i = 0; i < n - 1; i++) {
            scanf("%d%d", &ed[i].first, &ed[i].second);
            ed[i].first--;
            ed[i].second--;
        }
        vector<pair<int, int>> path(m);
        for (int i = 0; i < m; i++) {
            scanf("%d%d", &path[i].first, &path[i].second);
            path[i].first--;
            path[i].second--;
        }

        auto o = solve(ed, path);
        auto res = o.first;
        path = o.second;

        printf("%d\n", res);
        for (int i = 0; i < m; i++) {
            printf("%d %d\n", path[i].first + 1, path[i].second + 1);
        }
    }

#ifdef HOME
    cerr << "time = " << (clock() * 1. / CLOCKS_PER_SEC) << "\n";
#endif
    return 0;
}