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 all(v) v.begin(), v.end()
#define sz(v) int(v.size())
#define pii pair<int, int>
#define mp make_pair
#define f first
#define ll long long
#define ld long double
#define s second
#define vec vector<int>

using namespace std;

const int N = (int) 2000 + 10;
const int M = (int) 1e6 + 10;
const int K = (int) 500 + 10;
const int mod = (int) 1e9 + 7;
const ld EPS = 1e-9;
const ll LINF = (ll) 1e18;

int n, m;
vector<pii> g, e;
int ans;

vector<pii> solve(vector<pii> g, vector<pii> e) {
	vector<pii> cur;
	map<int, int> deg;
	for (auto it : g) {
		deg[it.f]++;
		deg[it.s]++;
	}
	int ver = -1;
	for (auto it : deg) {
		if (it.s == 1) { // degree = 1
			ver = it.f;
		}
	}
	int parent = -1;
	for (auto it : g) {
		if (it.f == ver || it.s == ver) {
			parent = (it.f ^ it.s ^ ver);
		}
	}
	if (ver == -1) {
		return e;
	}
	assert(ver != -1);
	vec leaf_paths;
	vector<pii> new_e;
	map<int, int> p;
	for (int i = 0; i < sz(e); i++) {
		if (e[i].f == e[i].s)
			continue;
		if (e[i].f == ver) {
			swap(e[i].f, e[i].s);
		}
		if (e[i].s == ver) {
			leaf_paths.pb(i);
		} else {
			new_e.pb(e[i]);
			p[sz(new_e) - 1] = i;
		}
	}
	vector<pair<pii, int> > relation;
	//ans += min(sz(leaf_paths), 2);
	while (sz(leaf_paths) >= 2) {
		int id_u = leaf_paths[sz(leaf_paths) - 1];
		int id_v = leaf_paths[sz(leaf_paths) - 2];
		leaf_paths.pop_back();
		leaf_paths.pop_back();
		new_e.pb(mp(e[id_u].f, e[id_v].f));
		relation.pb(mp(mp(id_u, id_v), sz(new_e) - 1));
	}
	if (sz(leaf_paths) == 1) {
		new_e.pb(mp(e[leaf_paths[0]].f, parent));		
		relation.pb(mp(mp(leaf_paths[0], leaf_paths[0]), sz(new_e) - 1));
	}
	vector<pii> new_g;
	for (auto it : g) {
		if (it.f != ver && it.s != ver) {
			new_g.pb(it);
		}
	}
	vector<pii> sub = solve(new_g, new_e);
	cur = e;
	for (auto it : p) {
		cur[it.s] = sub[it.f];
	}
	for (auto it : relation) {
		// it.f.f, it.f.s
		// it.f.f => (a -> ver)
		// it.f.s => (b -> ver)
		// it.s => (a -> b)
		if (it.f.f == it.f.s) {
			if (sub[it.s] != new_e[it.s]) { // parent -> a
				swap(cur[it.f.f].f, cur[it.f.f].s);
			}
			continue;
		}
		if (sub[it.s] == new_e[it.s]) { // a -> b
			// we should make a->ver, ver->b
			swap(cur[it.f.s].f, cur[it.f.s].s);
		} else { // b -> a
			// we should make b->ver, ver->a
			swap(cur[it.f.f].f, cur[it.f.f].s);
		}
	}
	#ifdef sony
	cout << "leaf = " << ver << "\ng:\n";
	for (auto it : g) {
		cout << it.f << ' ' << it.s << "\n";
	}
	cout << "e:\n";
	for (auto it : e) {
		cout << it.f << ' ' << it.s << "\n";
	}
	cout << "cur:\n";
	for (auto it : cur) {
		cout << it.f << ' ' << it.s << "\n";
	}
	cout << "sub:\n";
	for (auto it : sub) {
		cout << it.f << ' ' << it.s << "\n";
	}
	cout << "~~~~~~~~~~~~~\n";
	#endif
	return cur;
}

int p[N];
vec v[N];

void dfs(int ver, int par = -1) {
	for (auto it : v[ver]) {
		if (it != par) {
			p[it] = ver;
			dfs(it, ver);
		}
	}
}

pii f(int x, int y) {
	if (x > y)
		swap(x, y);
	return mp(x, y);
}

int main() {
	#ifdef sony
		freopen("input.txt", "r", stdin);
		freopen("output.txt", "w", stdout);
	#endif
	srand(time(0));
	cin >> n >> m;
	g.resize(n - 1);
	e.resize(m);
	for (int i = 0; i < n - 1; i++) {
		cin >> g[i].f >> g[i].s;
		v[g[i].f].pb(g[i].s);
		v[g[i].s].pb(g[i].f);
	}
	map<pii, int> cnt;
	for (int i = 0; i < m; i++) {
		cin >> e[i].f >> e[i].s;
		dfs(e[i].f);
		int x = e[i].s;
		while (1) {
			if (x == e[i].f) break;
			cnt[f(x, p[x])]++;
			x = p[x];
		}
	}
	for (auto it : cnt) ans += min(2, it.s);
	vector<pii> res = solve(g, e);
	cout << ans << "\n";
	for (auto it : res) {
		cout << it.f << ' ' << it.s << "\n";
	}
	return 0;
}