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;
#define maxn 2010
#define ll long long
#define db double
#define vi vector<int>
#define pb push_back
#define mod 998244353
#define fi first
#define pi pair<int, int>
#define se second
#define mp make_pair
ll ksm(ll a, ll b) {
   if (!b) return 1;
   ll ns = ksm(a, b >> 1);
   ns = ns * ns % mod;
   if (b & 1) ns = ns * a % mod;
   return ns;
}
// head
int n, m;
vi eg[maxn];
int dep[maxn];
int u[maxn], v[maxn], fa[maxn];
deque<int> tr[maxn];
int cnt[maxn];
int bg[maxn];
void dfs(int a) {
	for (auto v : eg[a]) {
		if (v == fa[a]) continue;
		dep[v] = dep[a] + 1, fa[v] = a;
		dfs(v);
	}
}
deque<int> gt(int a, int b) {
	deque<int> r, e;
	while (a != b) {
		if (dep[a] >= dep[b])
			r.pb(a), a = fa[a];
		else e.pb(-b), b = fa[b];
	}
	for (auto x : e)
		r.pb(x);
	return r;
}
vi ss[maxn];
int tp[maxn];
int pre[maxn];
int gp(int a) {
	if (pre[a] == a) return a;
	int nf = gp(pre[a]);
	tp[a] ^= tp[pre[a]], pre[a] = nf;
	return nf;
}
int fl[maxn];
int main() {
	cin >> n >> m;
	for (int i = 1; i < n; i++) {
		int u, v;
		scanf("%d%d", &u, &v);
		eg[u].pb(v), eg[v].pb(u);
	}
	dfs(1);
	for (int i = 1; i <= m; i++) {
		scanf("%d%d", &u[i], &v[i]), 
		tr[i] = gt(u[i], v[i]);
		for (auto s : tr[i]) {
			cnt[abs(s)]++;
			if (s < 0) ss[-s].pb(-i);
			else ss[s].pb(i);
		}
	}
	int ans = 0;
	for (int i = 1; i <= n; i++)
		ans += min(cnt[i], 2);
	cout << ans << endl;
	for (int i = 1; i <= m; i++)
		pre[i] = i;
	for (int i = 2; i <= n; i++) {
		if (ss[i].size() < 2) continue;
		memset(fl, 0, sizeof(fl));
		int nf = 0;
		for (auto v : ss[i]) {
			int ng = gp(abs(v));
			int ut = tp[abs(v)] ^ (v < 0);
			ut++;
			if (fl[ng] && fl[ng] != ut) nf = 1;
			fl[ng] = ut;
		}
		if (nf) continue;
		else {
			l1:int x1 = rand() % ss[i].size(), x2 = rand() % ss[i].size();
			if (x1 == x2) goto l1;
			int tt = ss[i][x1], mm = ss[i][x2];
			int nr = (tt < 0) ^ (mm < 0) ^ 1;
			tt = abs(tt), mm = abs(mm);
			int ufa = gp(tt), vfa = gp(mm);
			pre[ufa] = vfa, 
			tp[ufa] = tp[tt] ^ tp[mm] ^ nr;
		}
	}
	for (int i = 1; i <= m; i++) {
		gp(i);
		if (tp[i] == 1) swap(u[i], v[i]);
		printf("%d %d\n", u[i], v[i]);
	}

 	return 0;
}