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;
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
	*this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
// debug & operator << (debug & dd, P p) { dd << "(" << p.x << ", " << p.y << ")"; return dd; }

const int nax = 2005;
vector<int> edges[nax];
int parent[nax];
int h[nax];
vector<pair<int,int>> up[nax];
pair<int,int> query[nax];
set<int> dirs[nax];

void dfs(int a) {
	for(int b : edges[a]) {
		if(b != parent[a]) {
			parent[b] = a;
			h[b] = h[a] + 1;
			dfs(b);
		}
	}
}

int main() {
	int n, q;
	scanf("%d%d", &n, &q);
	for(int i = 0; i < n - 1; ++i) {
		int a, b;
		scanf("%d%d", &a, &b);
		edges[a].push_back(b);
		edges[b].push_back(a);
	}
	dfs(1);
	for(int id = 0; id < q; ++id) {
		int a, b;
		scanf("%d%d", &a, &b);
		query[id] = {a, b};
		while(a != b) {
			if(h[a] > h[b]) {
				up[a].emplace_back(id, 0);
				a = parent[a];
			}
			else {
				up[b].emplace_back(id, 1);
				b = parent[b];
			}
		}
	}
	for(int a = 1; a <= n; ++a) {
		debug() << imie(a) imie(up[a]);
	}
	int answer = 0;
	for(int a = 2; a <= n; ++a) {
		answer += min(2, (int) up[a].size());
	}
	printf("%d\n", answer);
	while(true) {
		bool done = false;
		for(int rep = 0; rep < 2 && !done; ++rep) {
			for(int a = 2; a <= n; ++a) {
				if((rep == 1 && (int) up[a].size() >= 1)
				|| (rep == 0 && (int) up[a].size() == 1 && (int) dirs[a].size() == 1)) {
					done = true;
					int must_be = 0;
					if((int) dirs[a].size() == 1) {
						must_be = *dirs[a].begin() ^ 1;
					}
					int path_id = up[a][0].first;
					int path_dir = up[a][0].second;
					if(path_dir != must_be) {
						swap(query[path_id].first, query[path_id].second);
					}
					debug() << imie(rep) imie(path_id) imie(query[path_id]);
					for(int b = 2; b <= n; ++b) {
						for(int i = 0; i < (int) up[b].size(); ++i) {
							if(up[b][i].first == path_id) {
								dirs[b].insert(up[b][i].second ^ (path_dir ^ must_be));
								swap(up[b][i], up[b].back());
								up[b].pop_back();
							}
						}
					}
					break;
				}
			}
		}
		if(!done) {
			break;
		}
	}
	for(int id = 0; id < q; ++id) {
		printf("%d %d\n", query[id].first, query[id].second);
	}
}