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 debug(x) cerr << #x << " " << (x) << endl
using namespace std;

const int N = 2005, M = 2005;

template <class T>
void read (T &x) {
	int sgn = 1;
	char ch;
	x = 0;
	for (ch = getchar(); (ch < '0' || ch > '9') && ch != '-'; ch = getchar()) ;
	if (ch == '-') ch = getchar(), sgn = -1;
	for (; '0' <= ch && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0';
	x *= sgn;
}

template <class T>
void write (T x) {
	if (x < 0) putchar('-'), write(-x);
	else if (x < 10) putchar(x + '0');
	else write(x / 10), putchar(x % 10 + '0');
}

struct edge {
	int to, nxt;
} tree[N << 1];
int n, m, head[N], cnt = 0;
void addedge (int u, int v) {
	edge e = {v, head[u]};
	tree[head[u] = cnt++] = e;
}

struct path {
	int u, v;
} ;
vector<path> vec;
vector<int> lch, rch, isroot;
vector<int> adj[N];

int par[N], tag[N];

void dfs1 (int u, int fa) {
	par[u] = fa;
	for (int i = head[u]; ~i; i = tree[i].nxt) {
		int v = tree[i].to;
		if (v != fa) dfs1(v, u);
	}
}

int lca (int u, int v) {
	stack<int> stk1, stk2;

	for (; u; u = par[u]) stk1.push(u);
	for (; v; v = par[v]) stk2.push(v);
	while (!stk1.empty() && !stk2.empty() && stk1.top() == stk2.top()) stk1.pop(), stk2.pop();
	if (!stk1.empty()) return par[stk1.top()];
	else return par[stk2.top()];
}

void dfs2 (int u, int fa) {
	for (int i = head[u]; ~i; i = tree[i].nxt) {
		int v = tree[i].to;
		if (v != fa) dfs2(v, u), tag[u] += tag[v];
	}
}

void dfs3 (int u, int fa) {
	for (int i = head[u]; ~i; i = tree[i].nxt) {
		int v = tree[i].to;
		if (v != fa) dfs3(v, u);
	}

	if (!fa) return ;
	vector<int> tmp;
	for (int i = 0; i < adj[u].size(); i++) {
		int id = adj[u][i];
		if (vec[id].u == vec[id].v) continue ;
		if (isroot[adj[u][i]]) tmp.push_back(adj[u][i]);
	}

	for (int i = (tmp.size() <= 1) ? 0 : 2; i < tmp.size(); i++) {
		if (vec[tmp[i]].u != u) swap(vec[tmp[i]].u, vec[tmp[i]].v);
		int v = vec[tmp[i]].v, s = vec.size();
		adj[v].push_back(s), adj[fa].push_back(s);

		path p = {fa, v};
		vec.push_back(p), lch.push_back(tmp[i]), rch.push_back(-1);
		isroot.push_back(1), isroot[tmp[i]] = 0;
	}

	if (tmp.size() <= 1) return ;
	if (vec[tmp[0]].u != u) swap(vec[tmp[0]].u, vec[tmp[0]].v);
	if (vec[tmp[1]].u != u) swap(vec[tmp[1]].u, vec[tmp[1]].v);
	int v1 = vec[tmp[0]].v, v2 = vec[tmp[1]].v, s = vec.size();
	adj[v1].push_back(s), adj[v2].push_back(s);
	path p = {v1, v2};
	vec.push_back(p), lch.push_back(tmp[0]), rch.push_back(tmp[1]);
	isroot.push_back(1), isroot[tmp[0]] = isroot[tmp[1]] = 0;
}

void dfs4 (int u) {
	if (~lch[u]) {
		if (vec[rch[u]].u == vec[u].v) swap(vec[lch[u]].u, vec[lch[u]].v);
		else if (vec[lch[u]].v == vec[u].u) swap(vec[lch[u]].u, vec[lch[u]].v);
		dfs4(lch[u]);
	}
	if (~rch[u]) {
		if (vec[rch[u]].u == vec[lch[u]].u) swap(vec[rch[u]].u, vec[rch[u]].v);
		if (vec[rch[u]].v == vec[lch[u]].v) swap(vec[rch[u]].u, vec[rch[u]].v);
		dfs4(rch[u]);
	}
}

int main () {
	read(n), read(m);
	for (int i = 1; i <= n; i++) head[i] = -1;
	for (int i = 1; i < n; i++) {
		int u, v;
		read(u), read(v);
		addedge(u, v), addedge(v, u);
	}

	dfs1(1, 0);
	for (int i = 1; i <= n; i++) tag[i] = 0;

	for (int i = 0; i < m; i++) {
		int u, v;
		read(u), read(v);
		path p = {u, v};
		vec.push_back(p), isroot.push_back(1);
		lch.push_back(-1), rch.push_back(-1);
		adj[u].push_back(i), adj[v].push_back(i);

		tag[u]++, tag[v]++, tag[lca(u, v)] -= 2;
	}

	dfs2(1, 0), dfs3(1, 0);
	for (int i = 0; i < vec.size(); i++) {
		if (isroot[i]) dfs4(i);
	}

	int ans = 0;
	for (int i = 1; i <= n; i++) ans += min(tag[i], 2);
	write(ans), putchar('\n');
	for (int i = 0; i < m; i++) {
		write(vec[i].u), putchar(' ');
		write(vec[i].v), putchar('\n');
	}
	return 0;
}