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 fi first
#define se second
#define mp make_pair
#define pb push_back
#define all(x) (x).begin (),(x).end()
#define sqrt(x) sqrt(abs(x))
#define re return
#define sz(x) ((int)(x).size ())
#define prev PREV
#define next NEXT

using ll = long long;
using ii = pair<int, int>;
using ld = long double;
using D = double;
using vi = vector<int>;
using vii = vector<ii>;
using vvi = vector<vi>;
using vs = vector<string>;

template<typename T> T abs (T x) { re x < 0 ? -x : x; }
template<typename T> T sgn (T x) { re x < 0 ? -1 : (x > 0 ? 1 : 0); }
template<typename T> T sqr (T x) { re x * x; }
template<typename T> T gcd (T a, T b) { re a ? gcd (b % a, a) : b; }

int n;
int m;
vii v[2000];
vi u[2000];
vii w[2000];
int ea[2000];
int eb[2000];
int cnt[2000][2];
int now[2000];
int was[2000];
//int last[2000];
//int ct;

int go (int x, int p, int z, int t) {
	if (x == z) re 1;
	for (int i = 0; i < sz (v[x]); i++) {
		int y = v[x][i].fi;
		int yi = v[x][i].se;
		if (y == p) continue;
		if (go (y, x, z, t)) {
			u[t].pb (yi);
			w[yi / 2].pb (mp (yi % 2, t));
			cnt[yi / 2][yi % 2]++;
			re 1;
		} 
	}
	re 0;
}

int go (int x) {
	vi can;
	for (int i = 0; i < sz (w[x]); i++)
		if (was[w[x][i].se] == 0)
			can.pb (w[x][i].se);
	if (can.empty ()) re 0;
	int xx = can[rand () % can.size ()];
//	last[xx] = ct;
	was[xx] = 1;
	vi need;
	now[xx] ^= 1;
	for (int i = 0; i < sz (u[xx]); i++) {
		int y = u[xx][i];
		cnt[y / 2][(y % 2) ^ now[xx]]++;
		cnt[y / 2][(y % 2) ^ now[xx] ^ 1]--;
		if (cnt[y / 2][0] + cnt[y / 2][1] > 1 && (cnt[y / 2][0] == 0 || cnt[y / 2][1] == 0)) need.pb (y / 2);
	}
	for (int i = 0; i < sz (need); i++) go (need[i]);
	re 0;
}

int main () {
	scanf ("%d%d", &n, &m);
	for (int i = 0; i < n - 1; i++) {
		int a, b;
		scanf ("%d%d", &a, &b); a--; b--;
		v[a].pb (mp (b, 2 * i));
		v[b].pb (mp (a, 2 * i + 1));
	}
	for (int i = 0; i < m; i++) {
		int a, b;
		scanf ("%d%d", &a, &b); a--; b--;
		go (a, a, b, i);
		ea[i] = a;
		eb[i] = b;
	}
	int ans = 0;
	for (int i = 0; i < n - 1; i++)
		ans += min (2, sz (w[i]));
	printf ("%d\n", ans);
	while (true) {
	    vi can;
//		int st = -1;
		for (int j = 0; j < n - 1; j++)
			if (cnt[j][0] + cnt[j][1] > 1 && (cnt[j][0] == 0 || cnt[j][1] == 0)) {
				can.pb (j);
//				st = j;
//				break;
			}
		if (can.empty ()) break;
		int st = can[rand () % can.size ()];
		memset (was, 0, sizeof (was));
//		ct++;
//		printf ("%d\n", st + 1);
		go (st);
	}
	for (int i = 0; i < m; i++)
		if (now[i])
			printf ("%d %d\n", eb[i] + 1, ea[i] + 1);
		else
			printf ("%d %d\n", ea[i] + 1, eb[i] + 1);	
//	cerr << clock () << endl;
	return 0;
}