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:
/* be name khoda */

// #define long_enable
#include <iostream>
#include <algorithm>
#include <cstring>
#include <numeric>
#include <vector>
#include <fstream>
#include <set>
#include <map>
using namespace std;

#ifdef long_enable
typedef long long int ll;
#else
typedef int ll;
#endif

typedef pair<ll, ll> pii;
typedef pair<pii, ll> ppi;
typedef pair<ll, pii> pip;
typedef vector<ll> vi;
typedef vector<pii> vpii;

#define forifrom(i, s, n) for (ll i = s; i < n; ++i)
#define forirto(i, n, e) for (ll i = (n) - 1; i >= e; --i)
#define fori(i, n) forifrom (i, 0, n)
#define forir(i, n) forirto (i, n, 0)

#define F first
#define S second
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define smin(a, b) a = min(a, (b))
#define smax(a, b) a = max(a, (b))

#define debug(x) cout << #x << " -> " << (x) << endl
#define debug2(x, y) cout << #x << ' ' << #y << " -> " << (x) << ' ' << (y) << endl
#define debug3(x, y, z) cout << #x << ' ' << #y << ' ' << #z << " -> " << (x) << ' ' << (y) << ' ' << (z) << endl
#define debug4(x, y, z, t) cout << #x << ' ' << #y << ' ' << #z << ' ' << #t << " -> " << (x) << ' ' << (y) << ' ' << (z) << ' ' << (t) << endl
#define debuga(x, n) cout << #x << " -> "; fori (i1_da, n) { cout << (x)[i1_da] << ' '; } cout << endl
#define debugaa(x, n, m) cout << #x << " ->\n"; fori (i1_daa, n) { fori (i2_daa, m) { cout << (x)[i1_daa][i2_daa] << ' '; } cout << '\n'; } cout << endl

const ll MOD = 1000000007;
const ll INF = 2000000000;
const long long BIG = 1446803456761533460LL;

#define XL (x << 1)
#define XR (XL | 1)
#define MD ((l + r) >> 1)
#define Add(a, b) a = ((a) + (b)) % MOD
#define Mul(a, b) a = (1LL * (a) * (b)) % MOD

// -----------------------------------------------------------------------

const ll maxn = 2010;

ll n, m, sum, vis[maxn], deg[maxn], P[maxn][maxn], par[maxn], ps[maxn], ht[maxn];
vi g[maxn];
pii O[maxn];

void dfs1(ll x, ll parx) {
    for (auto y : g[x]) if (y != parx) {
        ++deg[x];
        ht[y] = ht[x] + 1;
        par[y] = x;
        dfs1(y, x);
    }
}

void dfs2(ll x, ll parx) {
    for (auto y : g[x]) if (y != parx) {
        dfs2(y, x);
        sum += min(2, ps[y]);
        ps[x] += ps[y];
    }
}

ll LCA(ll a, ll b) {
    while (a != b) {
        if (ht[a] < ht[b]) swap(a, b);
        a = par[a];
    }
    return a;
}

void solve() {
    fori (i, n) if (!vis[i] && !deg[i]) {
        ll a = -1, b = -1;
        fori (j, m) if (P[i][j] != -1) a = b, b = j;
        if (b == -1) {
            vis[i] = true;
            deg[par[i]]--;
            solve();
        } else if (a == -1) {
            if (P[i][b] != i) {
                P[par[i]][b] = P[i][b];
                P[P[i][b]][b] = par[i];
                O[b] = {par[i], P[i][b]};
                vis[i] = true;
                deg[par[i]]--;
                solve();
                if (O[b].F == par[i]) O[b].F = i;
                else O[b].S = i;
            } else {
                vis[i] = true;
                deg[par[i]]--;
                solve();
            }
        } else {
            ll x = P[i][a], y = P[i][b];
            P[y][b] = P[i][b] = P[i][a] = -1;
            P[x][a] = y;
            P[y][a] = x;
            O[a] = {x, y};
            solve();
            if (O[a].F == x) {
                O[a] = {x, i};
                O[b] = {i, y};
            } else {
                O[b] = {y, i};
                O[a] = {i, x};
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);

    cin >> n >> m;
    fori (i, n - 1) {
        ll a, b; cin >> a >> b; --a, --b;
        g[a].eb(b), g[b].eb(a);
    }
    memset(P, -1, sizeof P);
    dfs1(0, 0);
    fori (i, m) {
        ll a, b; cin >> a >> b; --a, --b;
        O[i] = {a, b};
        P[a][i] = b, P[b][i] = a;
        ps[a]++, ps[b]++, ps[LCA(a, b)] -= 2;
    }

    dfs2(0, 0);
    cout << sum << '\n';

    solve();
    fori (i, m) {
        cout << O[i].F + 1 << ' ' << O[i].S + 1 << '\n';
    }

}