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;
const int maxn = 1e5;
int n, m, ans[maxn + 10], res, tot[maxn + 10];
int fa[maxn + 10], dep[maxn + 10];
vector<int> g[maxn + 10];
bool vis[maxn + 10];

struct data {
	int x, y, id;
};
vector<data> a;

void solve(vector<data> a) {
	int rt = 0, cnt = 0, lk = 0;
	for (int i = 1; i <= n; ++i)
		if (!vis[i]) {
			++cnt; int now = 0, tmp = 0;
			for (auto j: g[i])
				if (!vis[j]) {
					++now; tmp = j;
				}
			if (now <= 1) {
				rt = i; lk = tmp;
			}
		}
	auto tmp = a;
	if (cnt == 1) {
		return;
	}
	vector<data> b;
	bool fd = 0;
	for (auto i: a)
		if (i.x == rt && i.y == rt) continue;
		else {
			if (i.y == rt) {
				fd = 1;
				b.push_back((data){i.y, i.x, i.id});
			} else b.push_back(i);
		}
	if (fd) {
		solve(b);
		for (auto i: a)
			if (i.x != rt && i.y == rt) ans[i.id] ^= 1;
		return;
	}
	a.clear(); vector<data> c;
	for (auto i: b) {
		if (i.x == rt) a.push_back(i);
		else c.push_back(i);
	}
	if (a.empty()) {
		vis[rt] = 1; solve(c);
		return;
	}
	if (a.size() == 1) {
		vis[rt] = 1;
		c.push_back((data){lk, a[0].y, a[0].id});
		solve(c);
		return;
	}
	int fir = 0, fid, sec = 0, sid;
	for (auto i: a)
		if (!fir) {
			fir = i.y;
			fid = i.id;
		} else if (!sec) {
			sec = i.y;
			sid = i.id;
		} else c.push_back(i);
	c.push_back((data){fir, sec, fid});
	solve(c);
	ans[sid] = ans[fid]; ans[fid] ^= 1;
}

void dfs(int p) {
	dep[p] = dep[fa[p]] + 1;
	for (auto i: g[p])
		if (i != fa[p]) {
			fa[i] = p; dfs(i);
		}
}

void mark(int x, int y) {
	while (x != y) {
		if (dep[x] < dep[y]) swap(x, y);
		++tot[x]; x = fa[x];
	}
}

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i < n; ++i) {
		int l, r; scanf("%d%d", &l, &r);
		g[l].push_back(r); g[r].push_back(l);
	}
	for (int i = 1; i <= m; ++i) {
		int x, y; scanf("%d%d", &x, &y);
		a.push_back((data){x, y, i});
	}
	solve(a);
	for (auto &i: a)
		if (ans[i.id]) swap(i.x, i.y);
	dfs(1);
	for (auto i: a)
		mark(i.x, i.y);
	for (int i = 2; i <= n; ++i)
		res += min(tot[i], 2);
	printf("%d\n", res);
	for (auto i: a)
		printf("%d %d\n", i.x, i.y);
}