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;
typedef long long ll;
typedef pair<int, int> pii;

#define A first
#define B second

int n, m, s[2005], t[2005], ans[2005];
bool ok[2005][2005][2];
vector<int> g[2005];
vector<int> p[2005];
int cur;
int ct[2005][2005];
vector<pii> e;
set<pii> r[2005][2005];
queue<pii> q;

bool dfs(int v, int w, int f = -1) {
	if (v == w) {
		p[cur].push_back(w);
		return 1;
	}

	for (int u : g[v]) {
		if (u == f)
			continue;
		bool b = dfs(u, w, v);
		if (b) {
			p[cur].push_back(v);
			return 1;
		}
	}

	return 0;
}

void ins(int a, int b, int i) {
	if (a > b) {
		r[b][a].insert(pii(i, -1));
	} else {
		r[a][b].insert(pii(i, 1));
	}
}

void deledge(int a, int b, int i, int d) {
	if (a > b) {
		if (ok[b][a][0] && ok[b][a][1])
			return;
		r[b][a].erase(pii(i, -d));
		ok[b][a][1] = 1;
		if (r[b][a].size() == 1) {
			pii t = (*r[b][a].begin());
			// cout << t.A << ' ' << t.B << endl;
			q.push(t);
		}
	} else {
		if (ok[a][b][0] && ok[a][b][1])
			return;
		r[a][b].erase(pii(i, d));
		ok[a][b][0] = 1;
		if (r[a][b].size() == 1) {
			pii t = (*r[a][b].begin());
			t.B = -t.B;
			q.push(t);
		}
	}
}

void del(int i, int d) {
	// cout << "del" << ' ' << i << ' ' << d << endl;
	if (ans[i] != 0)
		return;
	ans[i] = d;
	for (int j = 0; j < p[i].size()-1; ++j) {
		int u = p[i][j], v = p[i][j+1];
		if (d == -1)
			swap(u, v);
		//deleting u -> v
		deledge(u, v, i, d);
	}
}

int main() {
	int sum = 0;
	cin >> n >> m;
	for (int i = 0; i < n-1; ++i) {
		int a, b;
		cin >> a >> b;
		a--; b--;
		if (a > b)
			swap(a, b);
		e.push_back(pii(a, b));
		g[a].push_back(b);
		g[b].push_back(a);
	}

	for (int i = 0; i < m; ++i) {
		cin >> s[i] >> t[i];
		s[i]--; t[i]--;
		cur = i;
		dfs(s[i], t[i]);
		reverse(p[i].begin(), p[i].end());
		for (int k = 0; k < p[i].size()-1; ++k) {
			ins(p[i][k], p[i][k+1], i);
		}
	}

	for (int i = 0; i < n-1; ++i) {
		sum += min(2, (int)r[e[i].A][e[i].B].size());
		/* for (pii u : r[e[i].A][e[i].B])
			cout << u.A << ' ' << u.B << ' ';
		cout << endl; */
	}

	cout << sum << endl;

	while (true) {
		bool z = 1;
		for (int i = 0; i < m; ++i)
			if (ans[i] == 0)
				z = 0;
		if (z)
			break;

		while (!q.empty()) {
			pii k = q.front();
			q.pop();
			del(k.A, k.B);
		}

		for (int i = 0; i < m; ++i) {
			if (ans[i] == 0) {
				del(i, 1);
				break;
			}
		}
	}

	for (int i = 0; i < m; ++i) {
		if (ans[i] == 1)
			cout << s[i]+1 << ' ' << t[i]+1 << endl;
		else
			cout << t[i]+1 << ' ' << s[i]+1 << endl;
	}
}