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 pa pair<int,int>
#define pb push_back
#define se second
#define fi first
using namespace std;
const int N=2005;
bool vis[N],co[N];
int p[N],sz[N];
vector<pa> to[N];
int n,m,ans,rm[N];
vector<int> e[N];
pa get(int x){
	if (p[x]==x) return pa(x,0);
	pa pr=get(p[x]);
	pr.se^=co[x];
	return pr;
}
vector<pa> solve(int x){
	vis[x]=1;
	vector<pa> cur;
	for (int i=0;i<to[x].size();i++)
		if (rm[to[x][i].fi]!=x)
			cur.push_back(to[x][i]);
	for (int i=0;i<e[x].size();i++){
		int to=e[x][i];
		if (vis[to]) continue;
		vector<pa> tmp=solve(to);
		if (tmp.size()==1) ans++;
		else if (tmp.size()){
			ans+=2;
			map<int,int> mp;
			for (int j=0;j<tmp.size();j++){
				pa x=tmp[j];
				pa tt=get(x.fi);
				int c=tt.se^x.se;
				mp[tt.fi]|=(1<<c);
			}
			int fl=0;
			map<int,int>::iterator it;
			for (it=mp.begin();it!=mp.end();it++)
				if (it->second==3){
					fl=1; break;
				}
			if (!fl){
				it=mp.begin();
				pa x=*it,y=*(++it);
				if (sz[x.fi]>sz[y.fi]) swap(x,y);
				p[x.fi]=y.fi; sz[y.fi]+=sz[x.fi];
				co[x.fi]=((x.se!=y.se)^1);
			}
		}
		for (int j=0;j<tmp.size();j++)
			if (rm[tmp[j].first]!=x)
				cur.push_back(tmp[j]);
	}
	return cur;
}
int fa[N],T;
int IN[N],OUT[N];
bool isfa(int x,int y){
	return IN[x]<=IN[y]&&IN[y]<=OUT[x];
}
int lca(int x,int y){
	for (;!isfa(x,y);x=fa[x]);
	return x;
}
void dfs1(int x,int y){
	fa[x]=y; IN[x]=++T;
	for (int i=0;i<e[x].size();i++)
		if (e[x][i]!=y) dfs1(e[x][i],x);
	OUT[x]=++T;
}
int ga[N],gb[N];
int main(){
	scanf("%d%d",&n,&m);
	for (int i=1;i<n;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		e[x].pb(y);	e[y].pb(x);
	}
	dfs1(1,0);
	for (int i=1;i<=m;i++){
		scanf("%d%d",&ga[i],&gb[i]);
		to[ga[i]].pb(pa(i,0));
		to[gb[i]].pb(pa(i,1));
		rm[i]=lca(ga[i],gb[i]);
	}
	for (int i=1;i<=m;i++)
		p[i]=i,sz[i]=1;
	solve(1);
	printf("%d\n",ans);
	for (int i=1;i<=m;i++){
		pa t=get(i);
		if (t.se==0) printf("%d %d\n",ga[i],gb[i]);
		else printf("%d %d\n",gb[i],ga[i]);
	}
}