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<vector>
#include<set>
int N,M,A[2010],B[2010],a[2010],b[2010];
struct edge{int to,val;edge*next;}E[40010],*ne=E,*fir[2010],*fir2[2010];
void link(int u,int v,int val=0){*ne=(edge){v,val,fir[u]};fir[u]=ne++;}
void link2(int u,int v,int val=0){*ne=(edge){v,val,fir2[u]};fir2[u]=ne++;}
std::set<int>chs[2010];
bool edel[2010],cdel[2010];
int fa[2010],dep[2010],ans=0;
int lca(int x,int y){
	while(x!=y)dep[x]>dep[y]?x=fa[x]:y=fa[y];
	return x;
}
void tag2(int x,int y){
	while(x!=y){
		if(dep[x]>dep[y]){
			if(!edel[x])edel[x]=1,ans+=2;
			x=fa[x];
		}
		else{
			if(!edel[y])edel[y]=1,ans+=2;
			y=fa[y];
		}
	}
}
void init(int i){
	for(edge*e=fir[i];e;e=e->next)if(e->to!=fa[i]){
		fa[e->to]=i;
		dep[e->to]=dep[i]+1;
		init(e->to);
	}
}
void dfs(int i){
	for(edge*e=fir[i];e;e=e->next)if(e->to!=fa[i]){
		dfs(e->to);
	}
	if(i==1)return;
	//printf("i=%d\n",i);
	//printf("3=(%d,%d) cdel3=%d\n",a[3],b[3],cdel[3]);
	for(std::set<int>::iterator it=chs[i].begin(),it2;it!=chs[i].end();it=it2){
		it2=it;++it2;
		int id=*it;
		if(cdel[id]||a[id]==b[id])chs[i].erase(it);
		//else printf("%d(%d,%d)\n",id,a[id],b[id]);
	}
	if(!edel[i]){
		if(chs[i].size()==1){
			ans++;
			int id=*chs[i].begin();
			if(a[id]==i)a[id]=fa[i];
			else b[id]=fa[i];
			chs[fa[i]].insert(id);
			edel[i]=1;
		}
		if(chs[i].size()>1){
//			printf("%d\n",i);
			std::set<int>::iterator it=chs[i].begin();
			int id1=*it;
			int id2=*++it;
//			printf("%d %d\n",a[id1],b[id1]);
	//		printf("%d %d\n",a[id2],b[id2]);
			bool ty1=a[id1]==i,ty2=a[id2]==i;
			int to1=ty1?b[id1]:a[id1],to2=ty2?b[id2]:a[id2];
			int l=lca(i,to1)^lca(i,to2)^lca(to1,to2);
			tag2(i,l);
			link2(id1,id2,ty1==ty2);
			link2(id2,id1,ty1==ty2);
			cdel[id1]=1;
			chs[a[id1]].erase(id1);
			chs[b[id1]].erase(id1);
			if(ty2){
				chs[a[id2]].erase(id2);
				a[id2]=ty1?b[id1]:a[id1];
				chs[a[id2]].insert(id2);
			}
			else{
				chs[b[id2]].erase(id2);
				b[id2]=ty1?b[id1]:a[id1];
				chs[b[id2]].insert(id2);
			}
			for(it=chs[i].begin();it!=chs[i].end();++it){
				int id=*it;
				if(a[id]==i)a[id]=fa[i];
				else b[id]=fa[i];
				chs[fa[i]].insert(id);
			}
		}
	}
	else{
		for(std::set<int>::iterator it=chs[i].begin();it!=chs[i].end();++it){
			int id=*it;
			if(a[id]==i)a[id]=fa[i];
			else b[id]=fa[i];
			chs[fa[i]].insert(id);
		}
	}
}
bool cvis[2010],col[2010];
void cdfs(int i,int c){
	cvis[i]=1;
	col[i]=c;
	for(edge*e=fir2[i];e;e=e->next)
		if(!cvis[e->to])cdfs(e->to,c^e->val);
}
int main(){
//freopen("cf.in","r",stdin);
	scanf("%d%d",&N,&M);
	for(int i=1,u,v;i<N;i++)scanf("%d%d",&u,&v),link(u,v),link(v,u);
	for(int i=0;i<M;i++){
		scanf("%d%d",A+i,B+i);
		chs[a[i]=A[i]].insert(i);
		chs[b[i]=B[i]].insert(i);
	}
	init(1);
	dfs(1);
	printf("%d\n",ans);
	for(int i=0;i<M;i++)if(!cvis[i])cdfs(i,0);
	for(int i=0;i<M;i++){
		if(col[i])printf("%d %d\n",B[i],A[i]);
		else printf("%d %d\n",A[i],B[i]);
	}
}