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:
#ifndef BZ
#pragma GCC optimize "-O3"
#endif
#include <bits/stdc++.h>

#define FASTIO

#ifdef FASTIO
#define scanf abacaba
#define printf abacaba
#endif

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

using namespace std;


/*
ll pw(ll a, ll b) {
	ll ans = 1; while (b) {
		while (!(b & 1)) b >>= 1, a = (a * a) % MOD;
		ans = (ans * a) % MOD, --b;
	} return ans;
}
*/
const int MAXN = 2100;

int was[MAXN];

int p[MAXN];
int sz[MAXN];
int cc[MAXN];
vector<pair<int, int>> go[MAXN];
int n;
vector<int> eds[MAXN];
int rm[MAXN];

pair<int, int> get(int v) {
	if (p[v] == v)
		return make_pair(v, 0);
	else {
		auto pr = get(p[v]);
		pr.second ^= cc[v];
		return pr;
	}
}

int ans = 0;

vector<pair<int, int>> dfs1(int v) {
	was[v] = 1;
	vector<pair<int, int>> cur;
	for (auto p: go[v]) {
		if (rm[p.first] != v)
			cur.push_back(p);
	}
	for (int u: eds[v]) {
		if (was[u])
			continue;
		auto tmp = dfs1(u);
		if (tmp.size() == 1) {
			++ans;
		}
		else if (tmp.size() >= 2) {
			ans += 2;
			map<int, int> mm;
			for (auto x: tmp) {
				auto tt = get(x.first);
				int c = tt.second ^ x.second;
				mm[tt.first] |= (1 << c);
			}
			int fl = 0;
			for (auto x: mm) {
				if (x.second == 3) {
					fl = 1;
					break;
				}
			}
			if (!fl) {
				assert(mm.size() >= 2);
				pair<int, int> x = *mm.begin();
				pair<int, int> y = *(next(mm.begin()));
				if (sz[x.first] > sz[y.first])
					swap(x, y);
				if (x.second == y.second) {
					p[x.first] = y.first;
					cc[x.first] = 1;
					sz[y.first] += sz[x.first];
				}
				else {
					p[x.first] = y.first;
					cc[x.first] = 0;
					sz[y.first] += sz[x.first];
				}
			}
		}
		for (auto x: tmp) {
			if (rm[x.first] != v)
				cur.push_back(x);
		}
	}
	return cur;
}

int ga[MAXN];
int tin[MAXN];
int tout[MAXN];
int pr[MAXN];
int gb[MAXN];
int tm1;

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

int lca(int a, int b) {
	while (!is_p(a, b))
		a = pr[a];
	return a;
}

void dfs0(int v, int p) {
	pr[v] = p;
	tin[v] = tm1++;
	for (int u: eds[v]) {
		if (u == p)
			continue;
		dfs0(u, v);
	}
	tout[v] = tm1;
}

int main() {
#ifdef FASTIO
	ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#endif
	int m;
	cin >> n >> m;
	for (int i = 0; i < n - 1; ++i) {
		int a, b;
		cin >> a >> b;
		--a, --b;
		eds[a].push_back(b);
		eds[b].push_back(a);
	}
	dfs0(0, -1);
	for (int i = 0; i < m; ++i) {
		int a, b;
		cin >> a >> b;
		--a, --b;
		ga[i] = a;
		gb[i] = b;
		go[a].push_back(make_pair(i, 0));
		go[b].push_back(make_pair(i, 1));
		rm[i] = lca(a, b);
	}
	for (int i = 0; i < m; ++i)
		p[i] = i, sz[i] = 1;
	dfs1(0);
	cout << ans << "\n";
	for (int i = 0; i < m; ++i) {
		auto t = get(i);
		if (t.second == 0)
			cout << ga[i] + 1 << " " << gb[i] + 1 << "\n";
		else
			cout << gb[i] + 1 << " " << ga[i] + 1 << "\n";
	}
	return 0;
}