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;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
#define Rep(i,a,b) for(register int i=(a);i<=int(b);++i)
#define Dep(i,a,b) for(register int i=(a);i>=int(b);--i)
#define rep(i,a,b) for(register int i=(a);i<int(b);++i)
#define mem(x,v) memset(x,v,sizeof(x))
#define fi first
#define se second
#define gc getchar
#define pc putchar
inline ll read(){
    ll x=0,f=1;char c=gc();
    for(;!isdigit(c);c=gc())if(c=='-')f=-1;
    for(;isdigit(c);c=gc())x=(x<<1)+(x<<3)+(c^48);
    return x*f;
}
inline void write(ll x){if(x<0)x=-x,pc('-');if(x>=10)write(x/10);putchar(x%10+'0');}
inline void wri(ll x){write(x);pc(' ');}
inline void writeln(ll x){write(x);pc('\n');}
const int maxn = 5005;
struct Edge{
	int to,nxt;
	Edge(){}
	Edge(int to,int nxt):to(to),nxt(nxt){}
}edge[maxn*2];int first[maxn],nume;
void Addedge(int a,int b){
	edge[nume] = Edge(b,first[a]);
	first[a] = nume++;
}
vector<int> ed[maxn],st[maxn];
bool vis[maxn];int num[maxn],val[maxn];
int u[maxn],v[maxn],n,m;
bool dfs(int u,int id,int fa,int t){
	if(u==t) return true;
	for(int e=first[u];~e;e=edge[e].nxt){
		int v=edge[e].to;
		if(v!=fa && dfs(v,id,u,t)){
			ed[id].push_back(e);
			st[e>>1].push_back(id);
			return true;
		}
	}return 0;
}
int main(){
	n = read(),m = read();nume = 2;
	memset(first,-1,sizeof(first));
	rep(i,1,n){
		int a = read(),b = read();
		Addedge(a,b);
		Addedge(b,a);
	}
	Rep(i,1,m){
		u[i] = read(),v[i] = read();
		dfs(u[i],i,0,v[i]);
	}int ans = 0;
	rep(i,1,n) num[i] = st[i].size(),ans += min(2,num[i]);
	writeln(ans);
	for(;;){
		int x;
		for(x=1;x<n;++x) if(num[x]==1 && vis[x<<1]!=vis[x<<1|1]) break; 
		if(x==n){
			for(x=1;x<n && !num[x];++x);
			if(x==n) break;
		}
		while(val[st[x].back()]) st[x].pop_back();
		int p = st[x].back(),rev = 0;
		val[p] = true;
		auto it=ed[p].begin();
		for(it=ed[p].begin();it!=ed[p].end();++it){
			if((*it)/2==x){
				if(vis[*it]) rev=1,swap(u[p],v[p]);
				break;
			}
		}
		for(it=ed[p].begin();it!=ed[p].end();++it)
			vis[*it^rev]=1,--num[*it>>1];
	}
	Rep(i,1,m) wri(u[i]),writeln(v[i]);
	return 0;
}