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<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<ctime>
#include<map>
#include<bitset>
#include<set>
#include<assert.h>
#define LL long long
#define mp(x,y) make_pair(x,y)
#define pll pair<long long,long long>
#define pii pair<int,int>
#define SZ(x) ((int)x.size())
using namespace std;
inline LL read()
{
	LL f=1,x=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int stack[20];
template<typename T>inline void write(T x)
{
	if(x<0){putchar('-');x=-x;}
    if(!x){putchar('0');return;}
    int top=0;
    while(x)stack[++top]=x%10,x/=10;
    while(top)putchar(stack[top--]+'0');
}
template<typename T>inline void pr1(T x){write(x);putchar(' ');}
template<typename T>inline void pr2(T x){write(x);putchar('\n');}
template<typename T>inline void chkmin(T &x,T y){x=x<y?x:y;}
template<typename T>inline void chkmax(T &x,T y){x=x>y?x:y;}
const int MAXN=2005;
vector<int> nxt[MAXN];
void ins(int x,int y){nxt[x].emplace_back(y);}
int n,m,fa[MAXN],in[MAXN],ot[MAXN],id;
void dfs(int x)
{
	in[x]=++id;
	for(auto p:nxt[x])if(p^fa[x])fa[p]=x,dfs(p);
	ot[x]=id;
}
bool intree(int x,int y){return in[x]>=in[y]&&in[x]<=ot[y];}//x in subtree y?
vector<pii> E;int dat[MAXN];
struct edge
{
	pii now;int px,py;
	edge(){}edge(pii _now,int _px,int _py){now=_now;px=_px;py=_py;}
}a[MAXN*2],A,B;int tp;
vector<int> newe,lin;
vector<pii> wr;
queue<int> li;int sum[MAXN];
bool ok[MAXN];
int main()
{
	n=read();m=read();
	for(int i=1;i<n;i++)
	{
		int x=read(),y=read();
		ins(x,y);ins(y,x);++dat[x];++dat[y];
	}dfs(1);
	for(int i=1;i<=m;i++)
	{
		int x=read(),y=read();
		E.emplace_back(mp(x,y));
	}int ans=0;
	for(int i=1;i<=n;i++)
	{
		int cnt=0;
		for(auto p:E)if(intree(p.first,i)^intree(p.second,i))++cnt;
		ans+=min(2,cnt);sum[i]=cnt;
	}pr2(ans);for(int i=2;i<=n;i++)if(dat[i]==1)li.push(i);
	for(auto p:E)a[++tp]=edge(p,0,0),newe.emplace_back(tp);
	while(!li.empty())
	{
		int x=li.front();li.pop();
		if(ok[x]||sum[x]<=1)
		{
			--dat[fa[x]];
			if(dat[fa[x]]==1)li.push(fa[x]);continue;
		}lin.clear();int sz=0,id1,id2;
		for(auto p:newe)
		{
			if(intree(a[p].now.first,x)^intree(a[p].now.second,x))
			{
				if(sz==0)++sz,A=a[p],id1=p;
				else if(sz==1)++sz,B=a[p],id2=p;
				else lin.emplace_back(p);
			}
			else lin.emplace_back(p);
		}
		if(!intree(A.now.first,x))swap(A.now.first,A.now.second),swap(A.px,A.py);
		if(!intree(B.now.first,x))swap(B.now.first,B.now.second),swap(B.px,B.py);
		int u=x,pre;
		while(!intree(A.now.second,u)&&!intree(B.now.second,u))ok[u]=1,pre=u,u=fa[u];
		if(A.now.second==B.now.second)
		{
			swap(A.now.first,A.now.second);swap(A.px,A.py);
			a[id1]=A;a[id2]=B;
			newe.clear();for(auto p:lin)newe.emplace_back(p);
		}
		else
		{
			edge atom=edge(mp(A.now.second,B.now.second),id1,id2);newe.clear();
			a[++tp]=atom;newe.emplace_back(tp);for(auto p:lin)newe.emplace_back(p);
		}
		--dat[fa[x]];if(dat[fa[x]]==1)li.push(fa[x]);
	}
	for(int i=tp;i>=1;i--)
	{
		if(!a[i].px)wr.emplace_back(a[i].now);
		else
		{
			A=a[a[i].px];B=a[a[i].py];
			if(a[i].now.first!=A.now.first)swap(A.now.first,A.now.second),swap(A.px,A.py);
			if(a[i].now.second!=B.now.second)swap(B.now.second,B.now.first),swap(B.px,B.py);
			a[a[i].px]=A;a[a[i].py]=B;
		}
	}reverse(wr.begin(),wr.end());
	for(auto p:wr)pr1(p.first),pr2(p.second);
	return 0;
}