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:
// Tenshi ni Fureta yo!

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
typedef unsigned int UI;
typedef pair<int, int> pii;

#define DEBUG(...) fprintf(stderr, __VA_ARGS__)
#define MP make_pair
#define fst first
#define snd second
#define SZ(u) ((int) (u).size())
#define ALL(u) (u).begin(), (u).end()

inline void proc_status()
{
	ifstream t("/proc/self/status");
	cerr << string(istreambuf_iterator<char>(t), istreambuf_iterator<char>()) << endl;
}

template<typename T> inline int chkmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; }
template<typename T> inline int chkmax(T &a, const T &b) { return b > a ? a = b, 1 : 0; }
template<typename T> inline T sqr(const T &val) { return val * val; }

namespace fastIO
{
	const int MAX_BUFFER_SIZE = 1 << 16;

	char buffer[MAX_BUFFER_SIZE], *cur = buffer, *ed = buffer;

	inline char getc() { return *(cur == ed ? ed = buffer + fread(buffer, 1, MAX_BUFFER_SIZE, stdin), cur = buffer : cur)++; }
}
using fastIO::getc;

template<typename T> inline T read()
{
	register T sum(0), fg(1);
	register char ch(getc());
	for(; !isdigit(ch); ch = getc()) if(ch == '-') fg = -1;
	for(;  isdigit(ch); ch = getc()) sum = sum * 10 - '0' + ch;
	return sum * fg;
}

// END tpl.

const int MAXN = (int) 1e4;

int n, m;

vector<int> adj[MAXN + 5];

struct walk
{
	int u, v;

	walk() { }
	walk(int _u, int _v): u(_u), v(_v) { }
}a[MAXN + 5];

inline void input()
{
	n = read<int>(), m = read<int>();
	for(int i = 1; i < n; ++i)
	{
		int u = read<int>(), v = read<int>();
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	for(int i = 1; i <= m; ++i) a[i].u = read<int>(), a[i].v = read<int>();
}

namespace TREE
{
	int dep[MAXN + 5], fa[MAXN + 5];

	inline void dfs(int u, int fa0)
	{
		dep[u] = dep[fa[u] = fa0] + 1;
		for(auto v : adj[u]) if(v != fa0) dfs(v, u);
	}

	int sum[MAXN + 5];

	inline int calc_ans()
	{
		dfs(1, 0);

		auto add = [] (int u, int v)
		{
			if(dep[u] < dep[v]) swap(u, v);
			while(dep[u] > dep[v]) ++sum[u], u = fa[u];
			while(u != v)
			{
				++sum[u], u = fa[u];
				++sum[v], v = fa[v];
			}
		};

		for(int i = 1; i <= m; ++i) add(a[i].u, a[i].v);

		int ans = 0;
		for(int i = 2; i <= n; ++i) ans += min(2, sum[i]);
		return ans;
	}
}

inline void solve()
{
	printf("%d\n", TREE::calc_ans());

	static int cut[MAXN + 5], fa[MAXN + 5], d[MAXN + 5], type[MAXN + 5];
	static vector<int> son[MAXN + 5];

	int M = m;
	auto cut_node = [&] (int u)
	{
		int t = adj[u].back();
		cut[u] = 1;

		static vector<int> ids;
		for(int i = 1; i <= M; ++i) if(!fa[i] && a[i].u != a[i].v && (a[i].u == u || a[i].v == u)) ids.push_back(i);

		while(SZ(ids) >= 2)
		{
			int p = ids.back(); ids.pop_back();
			int q = ids.back(); ids.pop_back();
			fa[p] = fa[q] = ++M;
			type[p] = 0;
			type[q] = 1;
			a[M] = walk(a[p].u == u ? a[p].v : a[p].u, a[q].u == u ? a[q].v : a[q].u);
		}
		if(!ids.empty())
		{
			int p = ids.back(); ids.pop_back();
			fa[p] = ++M;
			type[p] = 2;
			a[M] = walk(t, a[p].u == u ? a[p].v : a[p].u);
		}

		adj[t].erase(find(ALL(adj[t]), u));
		adj[u].clear();
	};

	for(int i = 1; i < n; ++i)
		for(int j = 1; j <= n; ++j) if(!cut[j] && SZ(adj[j]) == 1) { cut_node(j); break; }

	function<void(int)> dfs;
	dfs = [&dfs] (int u)
	{
		if(!fa[u]) d[u] = 0;
		else
		{
			if(type[u] == 2) d[u] = a[u].u != a[fa[u]].u && a[u].v != a[fa[u]].v;
			else
			{
				if((type[u] ^ d[fa[u]]) == 0) d[u] = a[u].u != a[fa[u]].u;
				else d[u] = a[u].v != a[fa[u]].v;
			}
		}
		if(d[u]) swap(a[u].u, a[u].v);
		for(auto v : son[u]) dfs(v);
	};

	for(int i = 1; i <= M; ++i) if(fa[i]) son[fa[i]].push_back(i);
	for(int i = 1; i <= M; ++i) if(!fa[i]) dfs(i);

	for(int i = 1; i <= m; ++i) printf("%d %d\n", a[i].u, a[i].v);
}

int main()
{
#ifdef K_ON
	freopen("E.in", "r", stdin);
	freopen("E.out", "w", stdout);
#endif

	input();
	solve();

	return 0;
}