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<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cassert>
#include<ctime>
#define cmin(a,b) (a>(b)?a=(b),1:0)
#define cmax(a,b) (a<(b)?a=(b),1:0)
#define dmin(a,b) ((a)<(b)?(a):(b))
#define dmax(a,b) ((a)>(b)?(a):(b))
namespace io
{
	int F()
	{
		int n=0,F=1;
		char ch;
		while((ch=getchar())!='-'&&(ch<'0'||ch>'9'));
		ch=='-'?F=0:n=ch-'0';
		while((ch=getchar())>='0'&&ch<='9')n=n*10+ch-'0';
		return F?n:-n;
	}
}
struct li
{
	int u,v;
}l[333333];
int pno;
struct edge
{
	int to;
	int next;
}e[333333];
int pe=111111;
int deg[111111];
void insert(int a,int to)
{
	e[pe]=(edge){to,e[a].next};
	e[a].next=pe++;
	deg[to]++;
}
int siz[111111],fa[111111],top[111111],dep[111111],son[111111];
void dfs(int o)
{
	siz[o]=1;
	int mx=0;
	for(register int p=e[o].next;p;p=e[p].next)
		if(e[p].to!=fa[o])
		{
			fa[e[p].to]=o;
			dep[e[p].to]=dep[o]+1;
			dfs(e[p].to);
			siz[o]+=siz[e[p].to];
			if(cmax(mx,siz[e[p].to]))son[o]=e[p].to;
		}
}
void dfs2(int o)
{
	for(register int p=e[o].next;p;p=e[p].next)
		if(e[p].to!=fa[o])
		{
			if(e[p].to==son[o])top[e[p].to]=top[o];
				else top[e[p].to]=e[p].to;
			dfs2(e[p].to);
		}
}
int lca(int u,int v)
{
	while(top[u]!=top[v])
		dep[top[u]]>dep[top[v]]?u=fa[top[u]]:v=fa[top[v]];
	return dep[u]>dep[v]?v:u;
}
int fir(int u,int v)
{
	if(lca(u,v)!=u)return fa[u];
	while(1)
	{
		if(top[u]==top[v])return son[u];
		if(u==fa[top[v]])return top[v];
		v=fa[top[v]];
	}	
}
struct ha
{
	int no;
	int next;
}h[777777];
int ph=111111;
void hin(int v,int no)
{
	h[ph]=(ha){no,h[v].next};
	h[v].next=ph++;
}
int ans[333333];
int re[333333];
int fr[333333];
int vis[333333];
int q[222222],hq,tq,inq[222222];
int cov[111111];
int max;
void dfs3(int o)
{
	for(register int p=e[o].next;p;p=e[p].next)
		if(e[p].to!=fa[o])dfs3(e[p].to),cov[o]+=cov[e[p].to];
	max+=dmin(cov[o],2);
}
int main()
{
	int n=io::F(),m=io::F();
	for(register int i=1;i<n;++i)
	{
		int x=io::F(),y=io::F();
		insert(x,y);
		insert(y,x);
	}
	dfs(1);
	top[1]=1;
	dfs2(1);
	for(register int i=1;i<=m;++i)
	{
		int u=io::F(),v=io::F();
		l[i]=(li){u,v};
		hin(u,i);
		hin(v,i);
	}
	pno=m;
	for(register int i=1;i<=n;++i)
		if(deg[i]==1)q[tq++]=i,inq[i]=1;
	for(;hq!=tq;++hq)
	{
		int pl=0;
		int x[3];
		for(register int p=h[q[hq]].next;p;p=h[p].next)
			if(!vis[h[p].no])
			{
				vis[h[p].no]=1;
				x[++pl]=h[p].no;
				if(pl==2)
				{
					pl=0;
					if(l[x[1]].v!=q[hq])std::swap(l[x[1]].u,l[x[1]].v),ans[x[1]]^=1;
					if(l[x[2]].u!=q[hq])std::swap(l[x[2]].u,l[x[2]].v),ans[x[2]]^=1;
					if(l[x[1]].u!=l[x[2]].v)
					{
						++pno;
						l[pno]=(li){l[x[1]].u,l[x[2]].v};
						hin(l[x[1]].u,pno);
						hin(l[x[2]].v,pno);
						fr[x[1]]=fr[x[2]]=pno;
					}
				}
			}
		if(pl==1)
		{
			if(l[x[1]].u!=q[hq])std::swap(l[x[1]].u,l[x[1]].v),ans[x[1]]^=1;
			int tmp=fir(l[x[1]].u,l[x[1]].v);
			if(tmp==l[x[1]].v)goto skip;
			++pno;
			l[pno]=(li){tmp,l[x[1]].v};
			hin(l[pno].u,pno);
			hin(l[pno].v,pno);
			fr[x[1]]=pno;
		}
		skip:;
		for(register int p=e[q[hq]].next;p;p=e[p].next)
			if(!inq[e[p].to]&&--deg[e[p].to]<=1)inq[e[p].to]=1,q[tq++]=e[p].to;
	}
	for(register int i=pno;i;--i)
		if(fr[i])re[i]=re[fr[i]]^ans[fr[i]];
	for(register int i=1;i<=m;++i)
		cov[l[i].u]++,cov[l[i].v]++,cov[lca(l[i].u,l[i].v)]-=2;
	dfs3(1);
	printf("%d\n",max);
	for(register int i=1;i<=m;++i)
		if(re[i])printf("%d %d\n",l[i].v,l[i].u);
			else printf("%d %d\n",l[i].u,l[i].v);
	return 0;
}