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<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
#define si scanf
#define so printf
#define N 100100
#define nxt t[j]
template<typename TP>inline bool rd(TP& r)
{
	r=0;
	bool mns=0;
	char tmp=getchar();
	while(tmp<'0'||tmp>'9')
    {
		if(tmp=='-')
			mns=1;
		if(tmp==EOF)
			return 0;
		tmp=getchar();
    }
	while('0'<=tmp&&tmp<='9')
    {
		r=r*10+tmp-'0';
		tmp=getchar();
    }
	if(mns) r=-r;
    return 1;
}
int n,m,nm,ans;
struct Graph
{
	int h[N],x[N*10],t[N*10],tot;
	inline void ade(int u,int v)
	{
		++tot;
		x[tot]=h[u];
		h[u]=tot;
		t[tot]=v;
	}
};
Graph g,ms;
int dep[N],f[N][24];
void GetDep(int now,int fa)
{
	dep[now]=dep[fa]+1;
	f[now][0]=fa;
	for(int j=g.h[now];j;j=g.x[j])
		if(g.nxt!=fa)
			GetDep(g.nxt,now);
}
inline int LCA(int u,int v)
{
	if(dep[u]<dep[v])
		swap(u,v);
	for(int k=20;k>=0;--k)
		if(dep[f[u][k]]>=dep[v])
			u=f[u][k];
	if(u==v)
		return u;
	for(int k=20;k>=0;--k)
		if(f[u][k]!=f[v][k])
			u=f[u][k],v=f[v][k];
	return f[u][0];
}
int vs[N*10][2],rev[N*10],vis[N*10],fr[N*10];
int d[N];
void dfs(int now,int fa)
{
	for(int j=g.h[now];j;j=g.x[j])
		if(g.nxt!=fa)
		{
			dfs(g.nxt,now);
			d[now]+=d[g.nxt];
		}
	if(fa)
		ans+=min(d[now],2);
	int lst=0;
	for(int j=ms.h[now];j;j=ms.x[j])
		if(!vis[ms.nxt])
		{
			vis[ms.nxt]=1;
		    if(vs[ms.nxt][0]==vs[ms.nxt][1])
				continue;
			if(lst)
			{
				if(vs[lst][1]!=now)
				{
					rev[lst]^=1;
					swap(vs[lst][0],vs[lst][1]);
				}
				if(vs[ms.nxt][0]!=now)
				{
					rev[ms.nxt]^=1;
					swap(vs[ms.nxt][0],vs[ms.nxt][1]);
				}
				fr[lst]=fr[ms.nxt]=++nm;
				vs[nm][0]=vs[lst][0],vs[nm][1]=vs[ms.nxt][1];
				ms.ade(vs[nm][0],nm),ms.ade(vs[nm][1],nm);
				lst=0;
			}
			else
				lst=ms.nxt;
		}
	if(lst)
	{
		if(vs[lst][0]!=now)
		{
			rev[lst]^=1;
			swap(vs[lst][0],vs[lst][1]);
		}
		fr[lst]=++nm;
		vs[nm][0]=fa,vs[nm][1]=vs[lst][1];
		ms.ade(vs[nm][0],nm),ms.ade(vs[nm][1],nm);
	}
}
int main()
{
	rd(n),rd(m);
	for(int i=2,u,v;i<=n;++i)
	{
		rd(u),rd(v);
		g.ade(u,v);
		g.ade(v,u);
	}
	GetDep(1,0);
	for(int k=1;k<=20;++k)
		for(int i=1;i<=n;++i)
			f[i][k]=f[f[i][k-1]][k-1];
	for(int i=1,lca;i<=m;++i)
	{
		rd(vs[i][0]),rd(vs[i][1]);
		ms.ade(vs[i][0],i),ms.ade(vs[i][1],i);
		lca=LCA(vs[i][0],vs[i][1]);
		++d[vs[i][0]],++d[vs[i][1]];
		d[lca]-=2;
    }
	nm=m;
	dfs(1,0);
	for(int i=nm;i;--i)
	{
		rev[i]^=rev[fr[i]];
		if(rev[fr[i]])
			swap(vs[i][0],vs[i][1]);
	}
	so("%d\n",ans);
	for(int i=1;i<=m;++i)
		so("%d %d\n",vs[i][0],vs[i][1]);
	return 0;
}