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 <stdio.h>
#include <vector>
using namespace std;
int fr[2010],ne[4010],v[4010],bs=0;
void addb(int a,int b)
{
	v[bs]=b;
	ne[bs]=fr[a];
	fr[a]=bs++;
}
int sd[2010],fa[2010],es[2010];
void dfs1(int u,int f)
{
	sd[u]=sd[f]+1;
	fa[u]=f;
	for(int i=fr[u];i!=-1;i=ne[i])
	{
		if(v[i]!=f)
		{
			es[u]+=1;
			dfs1(v[i],u);
		}
	}
}
int lc[2010][2010],fz[2010];
int dfs2(int a,int b)
{
	if(lc[a][b])
		return lc[a][b];
	if(a==b)
		return lc[a][b]=a;
	if(sd[a]>sd[b])
		lc[a][b]=dfs2(fa[a],b);
	else
		lc[a][b]=dfs2(a,fa[b]);
	return lc[a][b];
}
int getd(int a,int b,int c)
{
	int z1=lc[a][c],z2=lc[a][b];
	return sd[z1]>sd[z2]?z1:z2;
}
vector<int> ve[2010];
int zu[2010],zv[2010],X[4010],Y[4010],yl[4010],jg[4010],dl[2010],sl=0,cs[2010];
bool de[4010],mz[2010];
void solve(int n)
{
	int he=0,ta=0;
	for(int i=1;i<=n;i++)
	{
		if(es[i]==0)
			dl[ta++]=i;
	}
	while(he<ta)
	{
		int u=dl[he++],f=fa[u],s=0;
		es[f]-=1;
		if(es[f]==0)dl[ta++]=f;
		for(int i=0;i<ve[u].size();i++)
		{
			int z=ve[u][i];
			if(X[z]==Y[z])
				de[z]=true;
			if(!de[z])s+=1;
		}
		if(s==0)continue;
		if(s==1||mz[u])
		{
			for(int i=0;i<ve[u].size();i++)
			{
				int z=ve[u][i];
				if(!de[z])
				{
					if(X[z]==u)X[z]=f;
					else Y[z]=f;
					ve[f].push_back(z);
				}
			}
			continue;
		}
		int a=-1,za,b,zb;
		for(int i=0;i<ve[u].size();i++)
		{
			int z=ve[u][i];
			if(!de[z])
			{
				int t=(X[z]==u)?Y[z]:X[z];
				if(a==-1)
					a=t,za=z;
				else
				{
					b=t;zb=z;
					break;
				}
			}
		}
		de[za]=de[zb]=true;
		yl[za]=yl[zb]=++sl;jg[za]=jg[zb]=-1;
		if(X[za]!=a)jg[za]=-2;
		if(X[zb]!=u)jg[zb]=-2;
		X[sl]=a;Y[sl]=b;
		ve[a].push_back(sl);ve[b].push_back(sl);
		for(int i=0;i<ve[u].size();i++)
		{
			int z=ve[u][i];
			if(!de[z]&&z!=za&&z!=zb)
			{
				if(X[z]==u)X[z]=f;
				else Y[z]=f;
				ve[f].push_back(z);
			}
		}
		ve[u].clear();
		int d=getd(u,a,b);
		while(u!=d)
		{
			mz[u]=true;
			u=fa[u];
		}
	}
}
int dfs3(int u)
{
	if(jg[u]>=0)
		return jg[u];
	int t=jg[u];
	jg[u]=dfs3(yl[u]);
	if(t==-2)
		jg[u]^=1;
	return jg[u];
}
int main()
{
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		fr[i]=-1;
	for(int i=0;i<n-1;i++)
	{
		int a,b;
		scanf("%d%d",&a,&b);
		addb(a,b);addb(b,a);
	}
	dfs1(1,0);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
			dfs2(i,j);
	}
	for(int i=1;i<=m;i++)
	{
		int a,b;
		scanf("%d%d",&a,&b);
		zu[i]=X[i]=a;zv[i]=Y[i]=b;
		ve[a].push_back(i);
		ve[b].push_back(i);
		int c=lc[a][b];
		while(a!=c)
		{
			cs[a]+=1;
			a=fa[a];
		}
		while(b!=c)
		{
			cs[b]+=1;
			b=fa[b];
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++)
		ans+=(cs[i]<2?cs[i]:2);
	sl=m;solve(n);
	printf("%d\n",ans);
	for(int i=1;i<=m;i++)
	{
		dfs3(i);
		if(jg[i]==0)
			printf("%d %d\n",zu[i],zv[i]);
		else
			printf("%d %d\n",zv[i],zu[i]);
	}
	return 0;
}