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<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#define MP make_pair
#define fi first
#define se second 
#define pb push_back
#define rep(i,a,b) for(i=a;i<=b;i++)
using namespace std;
const int N=2010;
struct node{
	int to,next;
};node edge[N*2];
int graph[N],tot;
int fa[N],father[N][17],dep[N];
int a[N],b[N],lca[N];
int f[N][2],c[N];
int ans[N];int vis[N];
vector<int> vec[N];
int n,m;int ANS;

void addedge(int i,int x,int y){
	edge[i].to=y;edge[i].next=graph[x];graph[x]=i;
}

int LCA(int x,int y){
	if(dep[x]<dep[y])	swap(x,y);
	int i,delta=dep[x]-dep[y];
	rep(i,0,15)	if(1<<i&delta)	x=father[x][i];
	if(x==y)	return x;
	for(i=15;i>=0;i--)	if(father[x][i]!=father[y][i])	{x=father[x][i];y=father[y][i];}
	return father[x][0];
}

void dfs(int x){
	int i,y;
	for(i=graph[x];i;i=edge[i].next){
		y=edge[i].to;
		if(y==fa[x])	continue;
		fa[y]=x;father[y][0]=x;dep[y]=dep[x]+1;
		dfs(y);
	}
}

void add(int x,int y,int id){
	while(x!=y)	{c[x]++;vec[x].pb(id);x=fa[x];}
}

void modify(int i,int ty){
	int x,y;
	x=a[i];y=lca[i];
	while(x!=y){c[x]--;f[x][0^ty]++;x=fa[x];}
	x=b[i];y=lca[i];
	while(x!=y){c[x]--;f[x][1^ty]++;x=fa[x];}
}


void solve(int id){
	int opt1,opt2,x,y,i,now;
	opt1=f[id][0]?1:0;
	rep(i,0,(int)vec[id].size()-1){
		now=vec[id][i];
		if(vis[now])	continue;
		break;
	}
	x=a[now];y=lca[now];opt2=1;
	while(x!=y){
		if(x==id) {opt2=0;break;}
		x=fa[x];
	}
	opt1^=opt2;
	ans[now]=opt1;vis[now]=1;
	modify(now,opt1);
}				

bool check(){
	int i;
	rep(i,1,n)	if(c[i]==1&&(!f[i][0]||!f[i][1])){
		solve(i);
		return true;
	}
	return false;
}

int main(){
//	freopen("a.in","r",stdin);
//	freopen("a.out","w",stdout);
	int i,j,x,y;
	scanf("%d%d",&n,&m);
	rep(i,1,n-1){
		scanf("%d%d",&x,&y);
		tot++;addedge(tot,x,y);
		tot++;addedge(tot,y,x);
	}
	dfs(1);
	rep(j,1,15)	rep(i,1,n)	father[i][j]=father[father[i][j-1]][j-1];
	rep(i,1,m){
		scanf("%d%d",&a[i],&b[i]);
		lca[i]=LCA(a[i],b[i]);
		add(a[i],lca[i],i);
		add(b[i],lca[i],i);
	}
	rep(i,1,n)	ANS+=min(c[i],2);
	printf("%d\n",ANS);
	rep(i,1,n)	if(c[i]<2)	c[i]=0;
	rep(i,1,m)	if(!vis[i]){
		ans[i]=0;vis[i]=1;
		modify(i,0);
		while(check());
	}
	rep(i,1,m){
		if(ans[i])	printf("%d %d\n",b[i],a[i]);
		else printf("%d %d\n",a[i],b[i]);
	}
	return 0;
}