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<cmath>
#include<algorithm>
using namespace std;
struct node
{
	int u,v;
}p[2005];
int n,m,i,j,k,l,id[2005],p1,p2,head[2005],adj[4005],nxt[4005],dep[2005],col[2005],size[2005],son[2005],tp[2005],fa[2005],ans;
bool v[2005];
void dfs(int x,int dad)
{
	id[x]=++i;
	size[x]=1;
	for(int y=head[x];y;y=nxt[y])
		if(adj[y]!=dad)
		{
			dep[adj[y]]=dep[x]+1;
			fa[adj[y]]=x;
			dfs(adj[y],x);
			size[x]+=size[adj[y]];
			if(!son[x]||size[adj[y]]>size[son[x]])
				son[x]=adj[y];
		}
}
void Dfs(int x,int dad)
{
	if(son[x])
	{
		tp[son[x]]=tp[x];
		Dfs(son[x],x);
	}
	for(int y=head[x];y;y=nxt[y])
		if(adj[y]!=dad&&adj[y]!=son[x])
		{
			tp[adj[y]]=adj[y];
			Dfs(adj[y],x);
		}
}
int lca(int a,int b)
{
	while(tp[a]!=tp[b])
	{
		if(dep[tp[a]]<dep[tp[b]])
			swap(a,b);
		a=fa[tp[a]];
	}
	return dep[a]<dep[b]?a:b;
}
int dis(int a,int b)
{
	return dep[a]+dep[b]-2*dep[lca(a,b)];
}
void work(int num)
{
	int i,j,k,x,y,z,p1,p2;
	if(num>=n)
	{
		for(i=1;i<=m;++i)
			col[i]=1;
		return;
	}
	for(i=1,j=0;i<=n;++i)
		if(!v[i]&&(j==0||dep[i]>dep[j]))
			j=i;
	v[j]=true;
	p1=p2=0;
	for(k=1;k<=m;++k)
		if((id[p[k].u]>=id[j]&&id[p[k].u]<id[j]+size[j])!=(id[p[k].v]>=id[j]&&id[p[k].v]<id[j]+size[j]))
		{
			if(!p1)
				p1=k;
			else if(!p2)
				p2=k;
			else
				break;
		}
	if(p1&&p2)
	{
		node a=p[p1],b=p[p2];
		x=(id[a.u]>=id[j]&&id[a.u]<id[j]+size[j]?a.v:a.u);
		y=(id[b.u]>=id[j]&&id[b.u]<id[j]+size[j]?b.v:b.u);
		p[p2]=(node){1,1};
		p[p1]=(node){x,y};
		work(num+1);
		z=col[p1];
		if(a.u==x)
			col[p1]=z;
		else
			col[p1]=(z==1?2:1);
		if(b.v==y)
			col[p2]=z;
		else
			col[p2]=(z==1?2:1);
		p[p1]=a,p[p2]=b;
	}
	else
		work(num+1);
}
int main()
{
	scanf("%d%d",&n,&m);
	for(i=1;i<n;++i)
	{
		scanf("%d%d",&j,&k);
		adj[i*2-1]=k;
		nxt[i*2-1]=head[j];
		head[j]=i*2-1;
		adj[i*2]=j;
		nxt[i*2]=head[k];
		head[k]=i*2;
	}
	for(i=1;i<=m;++i)
		scanf("%d%d",&p[i].u,&p[i].v);
	i=0;
	dfs(1,-1);
	tp[1]=1;
	Dfs(1,-1);
	for(i=1;i<n;++i)
	{
		j=(dep[adj[i*2]]>dep[adj[i*2-1]]?adj[i*2]:adj[i*2-1]);
		p1=p2=0;
		for(k=1;k<=m;++k)
			if((id[p[k].u]>=id[j]&&id[p[k].u]<id[j]+size[j])!=(id[p[k].v]>=id[j]&&id[p[k].v]<id[j]+size[j]))
			{
				if(!p1)
					p1=k;
				else if(!p2)
					p2=k;
				else
					break;
			}
		if(p1)
			++ans;
		if(p2)
			++ans;
	}
	printf("%d\n",ans);
	work(1);
	for(i=1;i<=m;++i)
		if(col[i]==1)
			printf("%d %d\n",p[i].u,p[i].v);
		else
			printf("%d %d\n",p[i].v,p[i].u);
	return 0;
}