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>

#define pb push_back
#define For(i, j, k) for (int i = j; i <= k; i++)

using namespace std;

const int N = 4010;

int n, k, m;
int Begin[N], Next[N], to[N], e = 1;

void add(int u, int v) {
	to[++e] = v, Next[e] = Begin[u], Begin[u] = e;
}

bool flag[N], used[N];
vector<int> P[N];

bool DFS(int o, int f, int aim, vector<int>& E) {
	if (o == aim) return true;
	for (int i = Begin[o]; i; i = Next[i]) {
		int u = to[i];
		if (u == f) continue;
		E.pb(i);
		if (DFS(u, o, aim, E)) return true;
		E.pop_back();
	}
	return false;
}

int cnt[N];
vector<int> cov[N];

int fr[N], de[N];

int main() {

	scanf("%d%d", &n, &m);

	k = n - 1;
	For(i, 1, k) {
		int u, v;
		scanf("%d%d", &u, &v);
		add(u, v), add(v, u);
	}
	For(i, 1, m) {
		int u, v;
		scanf("%d%d", &u, &v);
		fr[i] = u, de[i] = v;
		DFS(u, 0, v, P[i]);
		for (int x : P[i]) ++cnt[x / 2], cov[x / 2].pb(i);
	}

	int ans = 0;
	For(i, 1, k) ans += min(2, cnt[i]);

	while (true) {

		int id = 0;
		For(j, 1, k) if (cnt[j] == 1 && flag[j << 1] != flag[j << 1 | 1])
			id = flag[j << 1] ? j << 1 | 1 : j << 1;
		if (!id) {
			For(j, 1, k) if (cnt[j]) { id = j << 1; break; }
			if (!id) break;
		}

		int x = id / 2;
		while (used[cov[x].back()]) cov[x].pop_back();
		int y = cov[x].back();
		used[y] = true;

		bool rev = false;
		for (int s : P[y]) if (s / 2 == x) {
			rev = s != id;
			break;
		}
		if (rev) {
			swap(fr[y], de[y]);
			for (int &s : P[y]) s ^= 1;
		}

		for (int s : P[y]) --cnt[s / 2], flag[s] = true;
	}

	printf("%d\n", ans);
	For(i, 1, m) printf("%d %d\n", fr[i], de[i]);

	return 0;
}