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 maxn=2010;
struct node{
	int s,t;
}a[maxn];
int beg[maxn],tto[maxn<<1],nex[maxn<<1],e=1;
void putin(int s,int t){
	tto[++e]=t;
	nex[e]=beg[s];
	beg[s]=e;
}
vector<int> vec[maxn],edg[maxn];
int cnt[maxn];
bool color(int u,int t,int id,int fa){
	if(u==t) return 1;
	for(int i=beg[u];i;i=nex[i]){
		if(tto[i]==fa) continue;
		if(color(tto[i],t,id,u)){
			vec[i>>1].push_back(id);
			edg[id].push_back(i);
			return 1;
		}
	}
	return 0;
}
bool ok[maxn<<1],vis[maxn];
int main(){
	int n,m;
	scanf("%d%d",&n,&m);
	int s,t;
	for(int i=1;i<n;i++){
		scanf("%d%d",&s,&t);
		putin(s,t);
		putin(t,s);
	}
	for(int i=1;i<=m;i++){
		scanf("%d%d",&a[i].s,&a[i].t);
		color(a[i].s,a[i].t,i,-1);
	}
	int ans=0;
	for(int i=1;i<n;i++){
		cnt[i]=vec[i].size();
		ans+=cnt[i]<=2?cnt[i]:2;
	}
	int p;
	bool rev;
	while(1){
		for(p=1;p<n;p++){
			if(cnt[p]==1&&ok[p<<1]!=ok[p<<1|1])
				break;
		}
		if(p==n){
			for(p=1;p<n&&!cnt[p];p++);
			if(p==n) break;
		}
		while(vis[vec[p].back()]) vec[p].pop_back();
		int x=vec[p].back();
		rev=0;
		for(vector<int>::iterator it=edg[x].begin();it!=edg[x].end();it++){
			if((*it)/2==p){
				if(ok[*it]){
					rev=1;
					swap(a[x].s,a[x].t);
				}
				break;
			}
		}
		for(vector<int>::iterator it=edg[x].begin();it!=edg[x].end();it++){
			ok[(*it)^rev]=1;
			cnt[(*it)>>1]--;
		}
		vis[x]=1;
	}
	printf("%d\n",ans);
	for(int i=1;i<=m;i++)
		printf("%d %d\n",a[i].s,a[i].t);
	return 0;
}