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<bits/stdc++.h>
using namespace std;
const int N=2005;
struct edge{
	int v,u,f,d;
	inline edge(){}
	inline edge(int v,int u,int f,int d):v(v),u(u),f(f),d(d){}
}E[N*N];
int dd[N*N];
vector<int>e[N];
int dg[N],d[N],fa[N],de[N],vi[N],cnt[N],ans,nn;
void dfs(int v,int f){
	int s=e[v].size(),i=0,u,d=de[v]+1;
	for(;i!=s;++i){
		if((u=e[v][i])!=f){
			de[u]=d;
			dfs(u,fa[u]=v);
		}
	}
}
int dfs2(int v,int f){
	int s=e[v].size(),i=0,u,dd=d[v];
	for(;i!=s;++i){
		if((u=e[v][i])!=f){
			dd+=dfs2(u,v);
		}
	}
	if(dd){if(dd==1)++ans;else ans+=2;}
	return dd;
}
inline int lca(int v,int u){
	if(de[v]<de[u])swap(v,u);
	while(de[v]!=de[u])v=fa[v];
	while(v!=u){
		v=fa[v];
		u=fa[u];
	}
	return v;
}
inline void work(int a,int b,int v,int u){
//	printf("work %d %d %d %d\n",a,b,v,u);
	int i;
	for(i=2;i<=nn;++i)cnt[i]=0;
	if(de[a]<de[b])swap(a,b);
	while(de[a]!=de[b]){
		cnt[a] =1;a=fa[a];
	}
	while(a!=b){
		cnt[a] =1;a=fa[a];
		cnt[b] =1;b=fa[b];
	}
	if(de[v]<de[u])swap(v,u);
	while(de[v]!=de[u]){
		cnt[v]|=2;v=fa[v];
	}
	while(v!=u){
		cnt[v]|=2;v=fa[v];
		cnt[u]|=2;u=fa[u];
	}
//	for(i=2;i<=nn;++i)if(cnt[i]==3)printf("VI %d\n",i);
	for(i=2;i<=nn;++i)if(cnt[i]==3)vi[i]=1;
}
int main(){
	int n,m,t,td,p,l,v,u,i;
	scanf("%d%d",&n,&m);t=td=m;nn=n;
	for(i=1;i!=n;++i){
		scanf("%d%d",&v,&u);
		++dg[v];++dg[u];
		e[v].push_back(u);
		e[u].push_back(v);
	}
	dfs(1,0);
	for(i=1;i<=m;++i){
		scanf("%d%d",&v,&u);
		E[i].v=v;
		E[i].u=u;
		E[i].d=i;
		l=lca(v,u);
		++d[v];
		++d[u];
		d[l]-=2;
	}
	dfs2(1,0);
	printf("%d",ans);
	l=n;
	while(--l){
		for(v=1;v<=n;++v){
			if(dg[v]==1){
				break;
			}
		}
		p=e[v].size();
		for(i=0;i!=p;++i)if(dg[u=e[v][i]])break;
//		printf("\n===\nv=%d u=%d son=%d\n",v,u,(fa[v]==u)?v:u);
		--dg[v];
		--dg[u];
		p=0;
		for(i=1;i<=m;++i){
			if(E[i].v){
				if(E[i].u==v){E[i].u=E[i].v;E[i].v=v;}
				if(E[i].v==v)d[++p]=i;
			}
		}
//		printf("edge vi=%d\np=%d\n",vi[(fa[v]==u)?v:u],p);
		i=1;
		if(!vi[(fa[v]==u)?v:u]&&p>=2){
			i=3;
			work(v,E[d[1]].u,v,E[d[2]].u);
			if(E[d[1]].u==E[d[2]].u){
//				puts("qwq");
				E[d[1]].v=E[d[1]].u;
				E[d[1]].u=v;
				E[++t]=E[d[1]];E[t].f=0;
				E[++t]=E[d[2]];E[t].f=0;
				E[d[1]].v=E[d[2]].v=0;
			}else{
				E[++t]=E[d[1]];E[t].f=++td;
				E[++t]=E[d[2]];E[t].f=  td;
				E[d[1]]=edge(E[t-1].u,E[t].u,0,td);
				E[d[2]].v=0;
			}
		}
		for(;i<=p;++i){
//			printf("add %d\n",i);
			E[++t]=E[d[i]];
			if(u==E[t].u){
				E[t].f=0;
				E[d[i]].v=0;
			}else{
				E[t].f=++td;
				E[d[i]]=edge(u,E[t].u,0,td);
			}
		}
/*		for(i=1;i<=m;++i){
			printf("%d %d %d %d\n",E[i].v,E[i].u,E[i].f,E[i].d);
		}*/
	}
	for(i=1;i<=t;++i){
		if(E[i].v){
			dd[E[i].d]=i;
		}
	}
	for(i=1;i<=t;++i){
		E[i].f=dd[E[i].f];
	}/*
	for(i=1;i<=t;++i){
		printf("%d %d %d %d\n",E[i].v,E[i].u,E[i].f,E[i].d);
	}
	for(i=1;i<=m;++i){
		printf("%d ",dd[i]);
	}
	printf("\n");*/
	for(l=1;l<=m;++l){
		p=0;
		for(i=dd[l];i;i=E[i].f)d[++p]=i;
//		for(i=1;i<=p;++i)printf("(%d,%d) ",E[d[i]].v,E[d[i]].u);
		while(p--){
			if(E[d[p]].u==E[d[p+1]].v){
				swap(E[d[p]].v,E[d[p]].u);
			}
		}
		printf("\n%d %d",E[d[1]].v,E[d[1]].u);
	}
	return 0;
}