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 MX = 2005;

int n, m;
int fst[MX], nxt[MX*2], v[MX*2], lnum;
vector<pair<int, int> > ori;

template <typename T> void read(T &x)
{
	x = 0; char c = getchar(); bool f = 0;
	while(!isdigit(c) && c!='-') c = getchar();
	if(c == '-') f = 1, c = getchar();
	while(isdigit(c)) x = x*10+c-'0', c = getchar();
	if(f) x = -x;
}

void addeg(int nu, int nv)
{
	nxt[++lnum] = fst[nu];
	fst[nu] = lnum;
	v[lnum] = nv;
}

void input()
{
	read(n), read(m);
	for(int i=1; i<n; i++)
	{
		int a, b;
		read(a), read(b);
		addeg(a, b);
		addeg(b, a);
	}
	for(int i=1; i<=m; i++)
	{
		pair<int, int> tmp;
		read(tmp.first), read(tmp.second);
		ori.push_back(tmp);
	}
}

int vis[MX];

vector<int> solve(vector<int> rem, vector<int> fa, vector<pair<int, int> > qur)
{
	if(rem.size() == 0) return {};
	int x = rem.back();
	rem.pop_back();
	vector<pair<int, int> > nq, frm(qur.size());
	int lst = -1;
	for(int i=0; i<qur.size(); i++)
	{
		auto t = qur[i];
		if(t.first == t.second) continue;
		else if(t.first == x)
		{
			if(lst == -1) lst = i;
			else if(qur[lst].first == x)
			{
				frm[lst] = make_pair(nq.size(), -1);
				frm[i] = make_pair(nq.size(), +1);
				nq.push_back(make_pair(qur[lst].second, t.second));
				lst = -1;
			}
			else if(qur[lst].second == x)
			{
				frm[lst] = make_pair(nq.size(), +1);
				frm[i] = make_pair(nq.size(), +1);
				nq.push_back(make_pair(qur[lst].first, t.second));
				lst = -1;
			}
		}
		else if(t.second == x)
		{
			if(lst == -1) lst = i;
			else if(qur[lst].first == x)
			{
				frm[lst] = make_pair(nq.size(), -1);
				frm[i] = make_pair(nq.size(), -1);
				nq.push_back(make_pair(qur[lst].second, t.first));
				lst = -1;
			}
			else if(qur[lst].second == x)
			{
				frm[lst] = make_pair(nq.size(), +1);
				frm[i] = make_pair(nq.size(), -1);
				nq.push_back(make_pair(qur[lst].first, t.first));
				lst = -1;
			}
		}
		else
		{
			frm[i] = make_pair(nq.size(), +1);
			nq.push_back(t);
		}
	}
	if(lst != -1)
	{
		if(qur[lst].first == x)
		{
			frm[lst] = make_pair(nq.size(), +1);
			nq.push_back(make_pair(fa[x], qur[lst].second));
		}
		else
		{
			frm[lst] = make_pair(nq.size(), +1);
			nq.push_back(make_pair(qur[lst].first, fa[x]));
		}
	}
	vector<int> way = solve(rem, fa, nq), ret;
	for(int i=0; i<qur.size(); i++)
	{
		if(qur[i].first == qur[i].second) ret.push_back(+1);
		else ret.push_back(frm[i].second * way[frm[i].first]);
	}
	/*cout<<rem.size()+1<<" answer:"<<endl;
	for(int i=0; i<ret.size(); i++)
		if(ret[i] == +1) printf("%d %d\n", qur[i].first, qur[i].second);
		else printf("%d %d\n", qur[i].second, qur[i].first);*/
	return ret;
}

void work()
{
	vector<int> fa(n+1), dep(n+1), seq;
	function<void(int, int)> dfs = [&](int x, int f)
	{
		fa[x] = f;
		dep[x] = dep[f]+1;
		for(int i=fst[x]; i; i=nxt[i])
		{
			int y = v[i];
			if(y != f) dfs(y, x);
		}
		seq.push_back(x);
	};
	dfs(1, 0);
	reverse(seq.begin(), seq.end());
	auto ans = solve(seq, fa, ori);
	//cout<<"answer:"<<endl;
	function<void(int, int)> cover = [&](int x, int y)
	{
		while(x != y)
		{
			if(dep[x] < dep[y]) swap(x, y);
			vis[x]++;
			x = fa[x];
		}
	};
	for(int i=0; i<ori.size(); i++) cover(ori[i].first, ori[i].second);
	int sum = 0;
	for(int i=1; i<=n; i++) sum += min(2, vis[i]);
	printf("%d\n", sum);
	for(int i=0; i<ans.size(); i++)
		if(ans[i] == +1) printf("%d %d\n", ori[i].first, ori[i].second);
		else printf("%d %d\n", ori[i].second, ori[i].first);
}

int main()
{
	input();
	work();
	return 0;
}