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<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<algorithm>

using namespace std;

#define LL long long
#define fgx cerr<<"--------------"<<endl;
#define dgx cerr<<"=============="<<endl;

inline int read(){
	int x=0,f=1;char c=getchar();
	for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
	for(;isdigit(c);c=getchar()) x=x*10+c-'0';
	return x*f;
}
const int MAXN = 2010*2010;
const int INF = 2147483600;

int N,M; 
#define pii pair<int,int>
#define fr first
#define sc second
#define mp make_pair 
int Node[MAXN<<1],Next[MAXN<<1],Root[MAXN+1],cnt; bool Ers[MAXN+1],Rev[MAXN+1];
pii Es[MAXN+1]; int top;
#define pb push_back
inline void insert(int u,int v){ Node[++cnt]=v; Next[cnt]=Root[u]; Root[u]=cnt; }
vector<pii > S[MAXN+1];
int fa[MAXN+1],Nod[MAXN+1],tim;
int dep[MAXN+1]; int P[2][MAXN+1];
inline int LCA(int u,int v){
	if(dep[u]<dep[v]) swap(u,v);
	while(dep[u]>dep[v]) u=fa[u];
	while(u!=v) u=fa[u],v=fa[v]; return u;
}
inline void dfs(int k,int Fa){
	dep[k]=dep[Fa]+1;
	for(int x=Root[k];x;x=Next[x]){
		int v=Node[x]; if(v==Fa) continue;
		dfs(v,k);
	} ++tim; fa[k]=Fa; Nod[tim]=k; 
} int id; int lnk[MAXN+1];
inline void solve(int nwid){
	int k=Nod[nwid]; top=0;
	for(int i=0,sz=S[k].size();i<sz;i++){ pii n=S[k][i]; if(Ers[n.sc]) continue; if(P[n.fr^1][n.sc]==k) Rev[n.sc]=0,Ers[n.sc]=n.fr; else Es[++top]=n; }
	S[k].clear(); for(int i=1;i<=top;i++) S[k].pb(Es[i]); pii x,y; int Ad=-1;
	if(S[k].size()>=2){
		int sz=S[k].size()-1;
		x=S[k][sz],y=S[k][sz-1];
		S[k].pop_back(); S[k].pop_back();
		Ad=++id; P[0][id]=P[x.fr^1][x.sc],P[1][id]=P[y.fr^1][y.sc];
		Ers[x.sc]=Ers[y.sc]=1;
		//cout<<"Ad:"<<P[0][id]<<" "<<P[1][id]<<":"<<x.sc<<" "<<y.sc<<" "<<k<<endl;
		S[P[0][id]].pb(mp(0,id));
		S[P[1][id]].pb(mp(1,id));
	} for(int i=0,sz=S[k].size();i<sz;i++) {
		++id; pii n=S[k][i];
		P[n.fr^1][id]=P[n.fr^1][n.sc];
		P[n.fr][id]=fa[k]; Ers[n.sc]=1;
		S[P[0][id]].pb(mp(0,id));
		S[P[1][id]].pb(mp(1,id));
		lnk[n.sc]=id;
	}
	if(nwid==N) return ; solve(nwid+1); 
	if(Ad!=-1){
		if(Rev[Ad]) swap(x,y);
		Rev[x.sc]=x.fr^1; Ers[x.sc]=1;
		Rev[y.sc]=y.fr; Ers[y.sc]=1;
	} for(int i=0,sz=S[k].size();i<sz;i++) {
		pii n=S[k][i]; Rev[n.sc]=Rev[lnk[n.sc]];
	} return ;
} int ans=0; int fx[MAXN+1];
inline void dfsans(int k,int Fa){
	for(int x=Root[k];x;x=Next[x]){
		int v=Node[x]; if(v==Fa) continue;
		dfsans(v,k); ans+=min(fx[v],2); fx[k]+=fx[v];
	}
}

int main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	N=read(),M=read();
	for(int i=1;i<N;i++){
		int u=read(),v=read();
		insert(u,v); insert(v,u);
	} dfs(1,0); 
	for(int i=1;i<=M;i++){
		int u=read(),v=read();
		fx[u]++; fx[v]++; int p=LCA(u,v);
		fx[p]-=2;
		P[0][i]=u; P[1][i]=v;
		S[u].pb(mp(0,i));
		S[v].pb(mp(1,i));
	} id=M; dfsans(1,0); printf("%d\n",ans); solve(1);
	for(int i=1;i<=M;i++){
		if(Rev[i]) swap(P[0][i],P[1][i]);
		printf("%d %d\n",P[0][i],P[1][i]);
	}
	return 0;
}