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 <cmath>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <list>
#include <time.h>
#include <math.h>
#include <random>
#include <deque>
#include <queue>
#include <cassert>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <bitset>
#include <sstream>
#define ignore RIP

using namespace std;

typedef long long ll;

mt19937 rnd(228);

const int N = 2e3 + 7;

vector <int> g[N];
int par[N];
int tin[N], tout[N];
int cnt[N];

int tt = 0;

void dfs(int v, int pr)
{
    tin[v] = tt++;
    par[v] = pr;
    for (int to : g[v])
    {
        if (to != pr)
        {
            dfs(to, v);
        }
    }
    tout[v] = tt;
}

bool pr(int a, int b)
{
    return tin[a] <= tin[b] && tout[a] >= tout[b];
}

set <int> ans[N];
set <int> pp[N];
vector <int> cur[N];
int type[N][N];
int tmp[N];
bool u[N];
int ret[N];
bool ignore[N];

vector <pair <int, int> > ch_s;
vector <int> cnt_chs;
vector <int> cnt_us;

bool bad = false;

void solve(int i, int col)
{
    if (bad) return;
    if (u[i])
    {
        if (ret[i] != col)
        {
            bad = true;
        }
        return;
    }
    cnt_us.push_back(i);
    ret[i] = col;
    u[i] = true;
    vector <pair <int, int> > e;
    for (int x : cur[i])
    {
        cnt[x]--;
        ans[x].erase(i);
        cnt_chs.push_back(x);
        ch_s.push_back({x, i});
        if (cnt[x] == 1)
        {
            int ind = *ans[x].begin();
            if (type[ind][x] == type[i][x])
            {
                e.push_back({ind, col ^ 1});
            }
            else
            {
                e.push_back({ind, col});
            }
        }
    }
    for (auto c : e)
    {
        if (u[c.first] && ret[c.first] != c.second)
        {
            bad = true;
            return;
        }
    }
    for (auto c : e)
    {
        solve(c.first, c.second);
    }
}

int main()
{
#ifdef ONPC
    freopen("a.in", "r", stdin);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i < n; i++)
    {
        int a, b;
        cin >> a >> b;
        a--, b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    dfs(0, -1);
    vector <int> x(m), y(m);
    vector <int> inds(m);
    for (int i = 0; i < m; i++)
    {
        int s, t;
        cin >> s >> t;
        s--, t--;
        x[i] = s, y[i] = t;
        inds[i] = i;
        int x = s;
        while (!pr(x, t))
        {
            type[i][x] = 0;
            cur[i].push_back(x);
            ans[x].insert(i);
            cnt[x]++;
            x = par[x];
        }
        x = t;
        while (!pr(x, s))
        {
            type[i][x] = 1;
            cur[i].push_back(x);
            ans[x].insert(i);
            cnt[x]++;
            x = par[x];
        }
    }
    int as = 0;
    for (int i = 1; i < n; i++)
    {
        as += min(2, cnt[i]);
    }
    cout << as << '\n';
    while (true)
    {
        shuffle(inds.begin(), inds.end(), rnd);
        bool good = true;
        for (int i : inds)
        {
            if (!u[i] && !ignore[i])
            {
                bad = false;
                solve(i, 0);
                if (bad)
                {
                    good = false;
                    for (auto c : ch_s)
                    {
                        ans[c.first].insert(c.second);
                    }
                    for (int x : cnt_chs)
                    {
                        cnt[x]++;
                    }
                    for (int x : cnt_us)
                    {
                        u[x] = 0;
                    }
                    ignore[i] = true;
                }
                ch_s.clear(), cnt_chs.clear(), cnt_us.clear();
            }
        }
        if (good) break;
    }
    for (int i = 0; i < m; i++)
    {
        if (!ret[i])
        {
            cout << x[i] + 1 << ' ' << y[i] + 1 << '\n';
        }
        else
        {
            cout << y[i] + 1 << ' ' << x[i] + 1 << '\n';
        }
    }
}