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<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<string>
#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<unordered_set>
#include<array>
#include<map>
#include<iomanip>
#include<assert.h>
using namespace std;
typedef long long int llint;
typedef long double lldo;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase
/*
cout<<setprecision(20)
cin.tie(0);
ios::sync_with_stdio(false);
*/
const llint mod=998244353;
const llint big=2.19e15+1;
const long double pai=3.141592653589793238462643383279502884197;
const long double eps=1e-15;
template <class T,class U>void mineq(T& a,U b){if(a>b){a=b;}}
template <class T,class U>void maxeq(T& a,U b){if(a<b){a=b;}}
llint gcd(llint a,llint b){if(a%b==0){return b;}else return gcd(b,a%b);}
llint lcm(llint a,llint b){return a/gcd(a,b)*b;}
template<class T> void SO(T& ve){sort(ve.begin(),ve.end());}
template<class T> void REV(T& ve){reverse(ve.begin(),ve.end());}
llint LBI(vector<llint>&ar,llint in){return lower_bound(ar.begin(),ar.end(),in)-ar.begin();}
llint UBI(vector<llint>&ar,llint in){return upper_bound(ar.begin(),ar.end(),in)-ar.begin();}
vector<vector<int>>go;
vector<int>miti;
int dfs(int ter,int oya,int gol){
	miti.pub(ter);
	if(ter==gol){return 1;}
	for(auto it:go[ter]){
		if(it==oya){continue;}
		if(dfs(it,ter,gol)==1){return 1;}
	}
	if(gol!=-1){miti.pob();}
	return 0;
}
int main(void){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n,m,i,j,k,h;cin>>n>>m;
	//適当に決めても案外何とかなる説
	static int v[2000]={0};
	static int u[2000]={0};
	static int hen[2000][2000]={0};
	static int ban[2000][2000]={0};
	//小さい->大きい +1 大きい->小さい -1
	go.res(n);
	for(i=0;i<n-1;i++){
		int a,b;cin>>a>>b;
		a--;b--;
		go[a].pub(b);
		go[b].pub(a);
		ban[a][b]=i+1;
		ban[b][a]=-(i+1);
	}
	for(i=0;i<m;i++){
		cin>>v[i]>>u[i];
		v[i]--;u[i]--;
		miti.clear();
		dfs(v[i],-1,u[i]);
		//mitiに道が記されている
		for(j=0;j<(int)miti.size()-1;j++){
			int road=ban[miti[j]][miti[j+1]];
			if(road>0){hen[i][road]=1;}
			else{hen[i][-road]=-1;}
		}
	}
	//hen に1～nまでの向きが入った
	//てきとうにやる
	static int tota[2000]={0};//+1 -2
	static int noko[2000]={0};
	for(i=0;i<m;i++){
		for(j=1;j<n;j++){
			if(hen[i][j]!=0){noko[j]++;}
		}
	}
	static bool used[2000]={};
	for(i=0;i<m;i++){
		if(used[i]){continue;}
		used[i]=true;
		for(h=1;h<n;h++){
			if(hen[i][h]>0){tota[h]|=1;noko[h]--;}
			if(hen[i][h]<0){tota[h]|=2;noko[h]--;}
		}
		//残りが1の辺があればそれを探して向きをつける
		bool recha=false;
		do{
			recha=false;
			for(j=1;j<n;j++){
				if(noko[j]==1&&(tota[j]==1||tota[j]==2)){
					for(k=0;k<m;k++){
						if(used[k]){continue;}
						if(hen[k][j]==0){continue;}
						//会う辺を見つけた!
						recha=true;
						used[k]=true;
						if((tota[j]==1)==(hen[k][j]==1)){
							swap(u[k],v[k]);//逆転させる
							for(h=1;h<n;h++){
								if(hen[k][h]>0){tota[h]|=2;noko[h]--;}
								if(hen[k][h]<0){tota[h]|=1;noko[h]--;}
							}
						}else{
							for(h=1;h<n;h++){
								if(hen[k][h]>0){tota[h]|=1;noko[h]--;}
								if(hen[k][h]<0){tota[h]|=2;noko[h]--;}
							}
						}
						break;
					}
				}
			}
		}while(recha);
	}
	int tano=0;
	for(i=1;i<n;i++){
		if(tota[i]&1){tano++;}
		if(tota[i]&2){tano++;}
	}
	cout<<tano<<endl;
	for(i=0;i<m;i++){cout<<u[i]+1<<" "<<v[i]+1<<endl;}
	return 0;
}