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;

const int Nmax = 2005;

int x, y, n, m, Ids, answer;
int level[Nmax], t[Nmax];
bool done[Nmax], rev[Nmax<<2], erased[Nmax];
vector<int> v[Nmax];

struct Edge
{
    int x, y, id;
};
vector<Edge> edge;

void Erase(vector<int> &v, int val)
{
    v.erase(find(v.begin(), v.end(), val));
}

bool cmp(Edge a)
{
    return a.x == a.y;
}

void dfs(int node)
{
    for(auto son : v[node])
    {
        Erase(v[son], node);
        t[son] = node;
        level[son] = level[node] + 1;
        dfs(son);
    }
}

int best(int x, int y, int z)
{
    if(x == y || x == z) return x;
    if(y == z) return y;

    if(level[x] >= level[y] && level[x] >= level[z]) return best(t[x], y, z);
    if(level[y] > level[z]) return best(x, t[y], z);
    return best(x, y, t[z]);
}

void mark_all(int x, int y)
{
    while(x != y)
    {
        if(level[x] > level[y]) done[x] = 1, x = t[x];
            else done[y] = 1, y = t[y];
    }
}

void solve(vector<Edge> &w)
{
    int i, leaf = 0;
    for(i=1; !leaf; ++i)
        if(v[i].empty() && !erased[i]) leaf = i;

    if(leaf == 1) return;
    Erase(v[t[leaf]], leaf);
    erased[leaf] = 1;

    w.erase(remove_if(w.begin(), w.end(), cmp), w.end());

    int a=0, b=0;
    Edge e1, e2;
    bool change1, change2;

    vector<Edge> nw;

    for(auto e : w)
        if(e.x == leaf)
        {
            if(!a) e1 = e, change1 = 0, a = e.y;
                else if(!b) e2 = e, change2 = 0, b = e.y;
                    else nw.push_back({ t[leaf], e.y, e.id });
        }
        else if(e.y == leaf)
        {
            if(!a) e1 = e, change1 = 1, a = e.x;
                else if(!b) e2 = e, change2 = 1, b = e.x;
                    else nw.push_back({ e.x, t[leaf], e.id });
        }
        else nw.push_back(e);

    if(!a)
    {
        if(done[leaf]) answer += 2;
        solve(w);
        return;
    }

    if(done[leaf] || b) answer += 2;
        else answer ++;

    if(!b || done[leaf])
    {
        if(!change1) e1.x = t[leaf];
            else e1.y = t[leaf];
        nw.push_back(e1);

        if(b)
        {
            if(!change2) e2.x = t[leaf];
                else e2.y = t[leaf];
            nw.push_back(e2);
        }

        solve(nw);
        return;
    }

    int go = best(a, b, t[leaf]);
    mark_all(go, leaf);

    int curr = ++Ids;
    nw.push_back({a, b, Ids});

    solve(nw);

    rev[e1.id] = rev[curr] ^ change1 ^ 1;
    rev[e2.id] = rev[curr] ^ change2;
}

int main()
{
 //   freopen("input", "r", stdin);
 //   freopen("output", "w", stdout);
    cin.sync_with_stdio(false);

    cin >> n >> m;
    int i;
    for(i=1; i<n; ++i)
    {
        cin >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }

    dfs(1);

    for(i=1; i<=m; ++i)
    {
        cin >> x >> y;
        edge.push_back({x, y, i});
    }

    Ids = m;
    solve(edge);
    cout << answer << '\n';
    for(auto e : edge)
    {
        if(rev[e.id]) swap(e.x, e.y);
        cout << e.x << ' ' << e.y << '\n';
    }

    return 0;
}