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:
//by yjz
#include<bits/stdc++.h>
using namespace std;
#define FF first
#define SS second
#define PB push_back
#define MP make_pair
#define foreach(it,s) for(__typeof((s).begin()) it=(s).begin();it!=(s).end();it++)
#ifndef LOCAL
#define cerr if(0)cout
#endif
typedef long long ll;
const int mod=1e9+7;
//My i/o stream
struct fastio
{
	char s[100000];
	int it, len;
	fastio() {it=len=0;}
	inline char get()
	{
		if (it<len) return s[it++]; it=0;
		len=fread(s, 1, 100000, stdin);
		if (len==0) return EOF; else return s[it++];
	}
	bool notend()
	{
		char c=get();
		while (c==' '||c=='\n') c=get();
		if (it>0) it--;
		return c!=EOF;
	}
}_buff;
#define geti(x) x=getnum()
#define getii(x,y) geti(x),geti(y)
#define getiii(x,y,z) getii(x,y),geti(z)
#define puti(x) putnum(x),putchar(' ')
#define putii(x,y) puti(x),puti(y)
#define putiii(x,y,z) putii(x,y),puti(z)
#define putsi(x) putnum(x),putchar('\n')
#define putsii(x,y) puti(x),putsi(y)
#define putsiii(x,y,z) putii(x,y),putsi(z)
inline ll getnum()
{
	ll r=0; bool ng=0; char c; c=_buff.get();
	while (c!='-'&&(c<'0'||c>'9')) c=_buff.get();
	if (c=='-') ng=1, c=_buff.get();
	while (c>='0'&&c<='9') r=r*10+c-'0', c=_buff.get();
	return ng?-r:r;
}
template <class T> inline void putnum(T x)
{
	if (x<0) putchar('-'), x=-x;
	register short a[20]={}, sz=0;
	while (x) a[sz++]=x%10, x/=10;
	if(sz==0) putchar('0');
	for (int i=sz-1; i>=0; i--) putchar('0'+a[i]);
}
inline char getreal() {char c=_buff.get(); while (c<=32) c=_buff.get(); return c;}
ll qpow(ll x, ll k) {return k==0? 1: 1ll*qpow(1ll*x*x%mod,k>>1)*(k&1?x:1)%mod;}
const int maxn = 2011;
int n, m;
vector<int> con[maxn], ord;
int fa[maxn];
vector<pair<int,int> > E;
vector<pair<int,int> > V[maxn];
const int maxtot = 4000111;
int to[maxtot], toc[maxtot], ans[maxtot];
void dfs(int x, int pre=-1)
{
	for (auto u : con[x])
	{
		if (u==pre) continue;
		fa[u] = x;
		dfs(u, x);
	}
	ord.PB(x);
}
void addpath(int x, int y)
{
	int id = E.size();
	E.PB(MP(x, y));
	V[x].PB(MP(y, id));
	V[y].PB(MP(x, id));
}
int cnt;
bool vis[maxn*maxn];
bool cover(int x, int to, int pre=-1)
{
	if (x==to) return true;
	for (auto u : con[x])
	{
		if (u==pre) continue;
		if (cover(u, to, x))
		{
			cnt += !vis[x*n+u];
			vis[x*n+u] = 1;
			return true;
		}
	}
	return false;
}
int main()
{
	getii(n, m);
	for (int i=1; i<n; i++)
	{
		int x, y;
		getii(x, y);
		con[x].PB(y);
		con[y].PB(x);
	}
	dfs(1);
	for (int i=0; i<m; i++)
	{
		int x, y;
		getii(x, y);
		addpath(x, y);
	}
	static bool del[maxn];
	for (auto x : ord)
	{
		del[x] = 1;
		auto lst = MP(-1, -1);
		for (auto e : V[x])
		{
			if (del[e.FF]) continue;
//			cerr<<"edge:"<<x<<","<<e.FF<<","<<e.SS<<endl;
			if (lst.FF==-1) lst = e;
			else
			{
				to[e.SS] = E.size();
				toc[e.SS] = E[e.SS]!=MP(x, e.FF);
				to[lst.SS] = E.size();
				toc[lst.SS] = 1^(E[lst.SS]!=MP(x, lst.FF));
				addpath(lst.FF, e.FF);
				lst = MP(-1, -1);
			}
		}
		if (lst.FF!=-1)
		{
			to[lst.SS] = E.size();
			toc[lst.SS] = E[lst.SS]!=MP(x, lst.FF);
			addpath(fa[x], lst.FF);
		}
	}
	for (int i=int(E.size())-1; i>=0; i--)
	{
//		cerr<<"i="<<i<<" to="<<to[i]<<" toc="<<toc[i]<<" ("<<E[i].FF<<","<<E[i].SS<<")"<<endl;
		if (!to[i]) ans[i] = 0;
		else
		{
			ans[i] = ans[to[i]]^toc[i];
		}
	}
	for (int i=0; i<m; i++)
	{
		if (ans[i]) swap(E[i].FF, E[i].SS);
	}
	for (int i=0; i<m; i++)
	{
		cover(E[i].FF, E[i].SS);
	}
	putsi(cnt);
	for (int i=0; i<m; i++)
	{
		putsii(E[i].FF, E[i].SS);
	}
	return 0;
}