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 pb push_back
#define mp make_pair
#define rep(i,s,t) for(int i=s;i<=(t);++i)
using namespace std;

#define Pr(f,...) ///fprintf(stderr,f,##__VA_ARGS__),fflush(stderr)

const int N=4005;

set<int> edg[N]; 
vector<int> g[N];
// lc same rc diff
int del[N],n,deg[N],q,m,e[N][2],ch[N][2],w[N][2],o[N][2],dir[N];

void dfs(int v,int d){
	dir[v]=d;
	if(ch[v][0])dfs(ch[v][0],d^w[v][0]);
	if(ch[v][1])dfs(ch[v][1],d^w[v][1]);
}

void ins(int u,int v,int l=0,int r=0,int wl=0,int wr=0){
	Pr("ins %d,%d,%d,%d,%d,%d\n",u,v,l,r,wl,wr); 
	++m,e[m][0]=u,e[m][1]=v,ch[m][0]=l,ch[m][1]=r,w[m][0]=wl,w[m][1]=wr;
	if(e[m][0]==e[m][1])dfs(m,0);
	else edg[u].insert(m),edg[v].insert(m);
}

void construct(){
	int rem=n,root,adj;
	while(rem>1){
		rep(i,1,n)if(deg[i]==1&&!del[i])root=i;
		for(int d:g[root])if(!del[d])adj=d;
		--deg[adj],del[root]=1,--rem;

		Pr("root=%d,adj=%d\n",root,adj); 
		
		int p=0;
		vector<int> z; for(int i:edg[root])z.pb(i); 
		for(int i:z){
			if(!p){ p=i; continue; }
			int a=e[p][1]==root,b=e[i][1]==root;
			int u=e[p][!a],v=e[i][!b];
			edg[u].erase(p),edg[v].erase(i);
			ins(u,v,p,i,!a,b),p=0;
		}

		if(p){
			int z=(e[p][e[p][1]==root]=adj);
			if(e[p][0]!=e[p][1])edg[z].insert(p); else {
				edg[adj].erase(p); dfs(p,0); }
		}
	}
	for(int i=1;i<=q;++i)printf("%d %d\n",dir[i]?o[i][0]:o[i][1],dir[i]?o[i][1]:o[i][0]);
}

int dep[N],prt[N],cov[N];
void build(int v,int p){
	dep[v]=dep[p]+1,prt[v]=p;
	for(int d:g[v])if(d!=p)build(d,v);
}

void run(int u,int v){
	while(u!=v){
		if(dep[u]<dep[v])swap(u,v);
		++cov[u],u=prt[u];
	}
}

void count(){
	build(1,0); 
	rep(i,1,q){
		run(o[i][0],o[i][1]); 
	}
	int ans=0; 
	for(int i=2;i<=n;++i)ans+=min(2,cov[i]);
	printf("%d\n", ans);
}

int main(int argc,char *argv[]){
#ifdef CURIOUSCAT
	freopen("dat.in","r",stdin);
	freopen("my.out","w",stdout);
#endif
	scanf("%d%d",&n,&q); 	
	rep(i,1,n-1){
		int u,v;
		scanf("%d%d",&u,&v); 
		g[u].pb(v),g[v].pb(u); 
		++deg[u],++deg[v];
	}
	rep(i,1,q){
		scanf("%d%d",&o[i][0],&o[i][1]); 
		ins(o[i][0],o[i][1]);
	}
	count(); 
	construct();
	return 0;
}