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 <cstdlib>
#include <cstdio>
#include <set>
#define N 4011
using namespace std;
int fa[N],vist[N],indexx[N],tot,ans,que[N],d[N],n,m,used[N],Mark[N];
set<int> V[N];
set<int>::iterator it;
struct point{
	int sx,sy,x,y,sit;
	void init(int k){
		scanf("%d%d",&x,&y);
		sx=x,sy=y;
		V[x].insert(k);
		V[y].insert(k);
	}
	void tranc(int u,int v){
		if(x==u) x=v;
		if(y==u) y=v;
	}
}P[N];
struct apple{
	int v,nxt;
}edge[N*4];
void addedge(int x,int y){
	edge[++tot].v=y;
	edge[tot].nxt=indexx[x];
	indexx[x]=tot;
}
int dfs(int u,int fa,int t1,int t2){
	int ret=0;
	if(u==t1) ret++;
	if(u==t2) ret++;
	int t=indexx[u],vv;
	while(t){
		vv=edge[t].v;
		if(vv!=fa){
			int k=dfs(vv,u,t1,t2);
			ret+=k;
			if(k==2) Mark[(t+1)/2]=1;
		}
		t=edge[t].nxt;
	}
	return ret;
}
void solve(){
	int head=0,tail=0;
	for(int i=1;i<=n;i++){
		if(d[i]==1) que[++tail]=i;
	}
	while(head<tail){
		int u=que[++head];
		used[u]=1;
		int t=indexx[u],vv,flag=1;
		while(t){
			vv=edge[t].v;
			if(!used[vv]){
				flag=0;
				break;
			}
			t=edge[t].nxt;
		}
		if(flag) break;
		t=(t+1)/2;
		if(Mark[t]) ans+=2;
		d[vv]--;
		if(d[vv]==1) que[++tail]=vv;
		if(!V[u].size()) continue;
		if(V[u].size()==1 || Mark[t]){
			if(!Mark[t]) ans+=1;
			for(it=V[u].begin();it!=V[u].end();it++){
				int k=*it;
				P[k].tranc(u,vv);
				if(P[k].x!=P[k].y) V[vv].insert(k);
				else V[vv].erase(k);
			}
			V[u].clear();
		}
		else{
			ans+=2;
			int x=*V[u].begin();V[u].erase(V[u].begin());
			int y=*V[u].begin();V[u].erase(V[u].begin());
			if(P[x].y==u) P[x].sit^=1,swap(P[x].x,P[x].y);
			if(P[y].y==u) P[y].sit^=1,swap(P[y].x,P[y].y);
			V[P[x].y].erase(x),V[P[y].y].erase(y);
			P[x].x=P[y].y;fa[y]=x;
			if(P[x].x!=P[x].y) V[P[x].x].insert(x),V[P[x].y].insert(x);
			P[y].sit^=1^P[x].sit;
			dfs(u,0,P[x].x,P[x].y);
			for(it=V[u].begin();it!=V[u].end();it++){
				int k=*it;
				P[k].tranc(u,vv);
				if(P[k].x!=P[k].y) V[vv].insert(k);
				else V[vv].erase(k);
			}
		}
	}
}
int Find(int u){
	if(!fa[u]) return P[u].sit;
	if(vist[u]) return P[u].sit;
	vist[u]=1;
	P[u].sit^=Find(fa[u]);
	return P[u].sit;
}
int main(){
	int x,y;
	scanf("%d%d",&n,&m);
	for(int i=1;i<n;i++){
		scanf("%d%d",&x,&y);
		d[x]++,d[y]++;
		addedge(x,y);
		addedge(y,x);
	}
	for(int i=1;i<=m;i++){
		P[i].init(i);
	}
	solve();
	printf("%d\n",ans);
	for(int i=1;i<=m;i++){
		Find(i);
		if(P[i].sit) swap(P[i].sx,P[i].sy);
		printf("%d %d\n",P[i].sx,P[i].sy);
	}
	return 0;
}