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 clr(x) memset(x,0,sizeof x)
#define For(i,a,b) for (int i=(a);i<=(b);i++)
#define Fod(i,b,a) for (int i=(b);i>=(a);i--)
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define fi first
#define se second
#define outval(x) cerr<<#x" = "<<x<<endl
#define outtag(x) cerr<<"-----------------"#x"-----------------\n"
#define outarr(a,L,R) cerr<<#a"["<<L<<".."<<R<<"] = ";\
                    For(_x,L,R) cerr<<a[_x]<<" ";cerr<<endl;
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair <int,int> pii;
LL read(){
    LL x=0,f=0;
    char ch=getchar();
    while (!isdigit(ch))
        f=ch=='-',ch=getchar();
    while (isdigit(ch))
        x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return f?-x:x;
}
const int N=2005*2;
int n,m,k;
set <int> e[N];
int fa[N],depth[N];
void dfs(int x,int pre,int d){
	depth[x]=d,fa[x]=pre;
	for (auto y : e[x])
		if (y!=pre)
			dfs(y,x,d+1);
}
struct Link{
	int X,Y;
	int x,y;
	int del;
	vector <int> id;
}a[N];
vector <int> id[N];
void Ins(int x,int y,int i){
	if (depth[x]<depth[y])
		swap(x,y);
	while (depth[x]>depth[y])
		id[x].pb(i),x=fa[x];
	while (x!=y){
		id[x].pb(i),x=fa[x];
		id[y].pb(i),y=fa[y];
	}
	id[x].pb(i);
}
int vis[N][N];
int Calvis(int x,int a,int b,int pre=0){
	int c=0;
	for (auto y : e[x])
		if (y!=pre){
			int v=Calvis(y,a,b,x);
			c+=v;
			if (v>=2)
				vis[x][y]=vis[y][x]=1;
		}
	if (x==a)
		c++;
	if (x==b)
		c++;
	return c;
}
int main(){
	n=read(),m=k=read();
	For(i,1,n-1){
		int x=read(),y=read();
		e[x].insert(y),e[y].insert(x);
	}
	dfs(1,0,0);
	For(i,1,m){
		int x=a[i].x=a[i].X=read(),y=a[i].y=a[i].Y=read();
		a[i].id.pb(i);
		Ins(x,y,i);
	}
	int ans=0;
	For(_,1,n-1){
		int x=0;
		For(i,1,n)
			if (e[i].size()==1){
				x=i;
				break;
			}
		int y=*e[x].begin();
		vector <int> now;
		for (auto i : id[x])
			if (!a[i].del&&a[i].x!=a[i].y)
				now.pb(i);
		if (vis[x][y])
			ans+=2;
		else {
			if (now.size()>=2){
				int i=now[0],j=now[1];
				if (a[i].y!=x){
					swap(a[i].x,a[i].y);
					for (auto k : a[i].id)
						swap(a[k].X,a[k].Y);
				}
				if (a[j].x!=x){
					swap(a[j].x,a[j].y);
					for (auto k : a[j].id)
						swap(a[k].X,a[k].Y);
				}
				assert(a[i].y==x&&a[j].x==x);
				Calvis(x,a[i].x,a[j].y);
				k++;
				a[k].x=a[i].x;
				a[k].y=a[j].y;
				a[i].del=a[j].del=1;
				for (auto v : a[i].id)
					a[k].id.pb(v);
				for (auto v : a[j].id)
					a[k].id.pb(v);
				Ins(a[k].x,a[k].y,k);
				ans+=2;
			}
			else
				ans+=now.size();
		}
		for (auto i : now)
			(x==a[i].x?a[i].x:a[i].y)=y;
		e[x].erase(y),e[y].erase(x);
	}
	cout<<ans<<endl;
	For(i,1,m)
		printf("%d %d\n",a[i].X,a[i].Y);
	return 0;
}