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>
#define fo(i,a,b)for(int i=a,_e=b;i<=_e;++i)
#define pb push_back
using namespace std;
const int N=2005;
int n,m,x,y,ans;
int de[N],fa[N],c[N];
int du[N],d[N],u[N],v[N],u2[N],v2[N];
int f[N],w[N],fp[N];
vector<int>e[N],p[N];
bool no[N];
int F(int x){
	if(x==f[x])return x;
	int y=F(f[x]);
	w[x]^=w[f[x]];
	return f[x]=y;
}
void link(int x,int y,int z){
	int fx=F(x),fy=F(y);
	f[fx]=fy;w[fx]=w[x]^w[y]^z;
}
void dfs(int x){
	de[x]=de[fa[x]]+1;
	for(int i:e[x])if(i!=fa[x])
		fa[i]=x,dfs(i);
}
bool find(int i){
	return i==10||i==73;
}
int main(){
	cin>>n>>m;
	fo(i,2,n)cin>>x>>y,e[x].pb(y),e[y].pb(x),++du[x],++du[y];
	dfs(1);
	fo(i,1,m){
		cin>>x>>y;
		u2[i]=u[i]=x,v2[i]=v[i]=y;
		p[x].pb(i);
		p[y].pb(i);
		f[i]=i;
		for(;x!=y;x=fa[x]){
			if(de[x]<de[y])swap(x,y);
			++c[x];
		}
	}
	fo(i,2,n)ans+=min(2,c[i]);
	cout<<ans<<endl;
	int r=0;
	fo(i,1,n)if(du[i]==1)d[++r]=i;
	for(int l=0;x=d[++l],l<=r&&l<=n-1;){
		if(x==4||x==713){
			int kk=0;
		}
		int las=0,nx=0;
		for(int i:e[x]){
			--du[i];
			if(du[i]>0)nx=i;
			if(du[i]==1)d[++r]=i;
		}
		for(int i:p[x])if(!no[i]){
			if(!las)las=i;else{
				int z=1;
				if(v2[i]==x)z^=1;
				if(v2[las]==x)z^=1;
//				link(i,las,z);
				f[las]=i;w[las]=z;
				if(u2[i]==x){
					u2[i]=u2[las]==x?v2[las]:u2[las];
					p[u2[i]].pb(i);
				}else{
					v2[i]=u2[las]==x?v2[las]:u2[las];
					p[v2[i]].pb(i);
				}
				if(u2[i]==v2[i])no[i]=1;
				no[las]=1;
				if(find(i)||find(las)){
					int kk=0;
				}
				las=0;
			}
		}
		if(las){
			if(find(las)){
				int kk=0;
			}
			if(u2[las]==x)u2[las]=nx;else v2[las]=nx;
			if(u2[las]!=v2[las])p[nx].pb(las);else no[las]=1;
		}
	}
	fo(i,1,m){
		F(i);
		if(w[i]&1)printf("%d %d\n",v[i],u[i]);
		else printf("%d %d\n",u[i],v[i]);
	}
}