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 rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << (x) << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){return o<<"("<<p.fs<<","<<p.sc<<")";}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){o<<"sz = "<<vc.size()<<endl<<"[";for(const T& v:vc) o<<v<<",";o<<"]";return o;}

using P = pair<int,int>;
int N,Q,M;
vector<vector<int>> G;
vector<vector<int>> dist;
vector<int> X,Y;
map<P,int> xy2eid;
vector<vector<int>> e2paths;
vector<int> cnt;

vector<int> d_;
void dfs1(int v,int p=-1){
	if(p!=-1) d_[v] = d_[p]+1;
	for(int u:G[v]) if(u!=p) dfs1(u,v);
}

void calcdist(){
	rep(i,N){
		d_ = vector<int>(N,0);
		dfs1(i);
		dist.pb(d_);
	}
}

vector<int> dir;
bool done[2000][2];

void doit(int q,int d){
	assert(dir[q] == -1);
	dir[q] = d;
	int x = X[q], y = Y[q];
	if(d) swap(x,y);
	while(x!=y){
		int nx = -1;
		for(int u:G[x]) if(dist[u][y]<dist[x][y]) nx = u;
		int dir_eid = xy2eid[P(x,nx)];
		int eid = dir_eid%M;
		int dd = dir_eid/M;
		done[eid][dd] = 1;
		cnt[eid]--;
		x = nx;
	}
	x = X[q], y = Y[q];
	if(d) swap(x,y);

	while(x!=y){
		int nx = -1;
		for(int u:G[x]) if(dist[u][y]<dist[x][y]) nx = u;
		int dir_eid = xy2eid[P(x,nx)];
		int eid = dir_eid%M;
		int dd = dir_eid/M;

		if(!done[eid][dd^1] && cnt[eid]==1){
			int inveid = eid + (dd ? 0 : M);
			for(int dir_nq: e2paths[inveid]){
				int nq = dir_nq % Q;
				if(dir[nq] == -1){
					int nd = (dir_nq<Q ? 0 : 1);
					doit(nq,nd);
					break;
				}
			}
		}
		x = nx;
	}
}

int main(){
	cin>>N>>Q;
	M = N-1;
	G.resize(N);
	rep(i,N-1){
		int x,y;
		cin>>x>>y;
		x--,y--;
		G[x].pb(y);
		G[y].pb(x);
		xy2eid[P(x,y)] = i;
		xy2eid[P(y,x)] = i+M;
	}
	calcdist();
	X.resize(Q);Y.resize(Q);
	e2paths.resize(M*2);
	cnt.resize(M);
	rep(i,Q){
		cin>>X[i]>>Y[i];
		X[i]--,Y[i]--;
		int x = X[i], y = Y[i];
		while(x!=y){
			int nx = -1;
			for(int u:G[x]) if(dist[u][y]<dist[x][y]) nx = u;
			e2paths[xy2eid[P(x,nx)]].pb(i);
			e2paths[xy2eid[P(nx,x)]].pb(i+Q);
			x = nx;
		}
	}
	rep(i,M) cnt[i] = e2paths[i].size();

	dir = vector<int>(Q,-1);
	rep(i,Q) if(dir[i] == -1){
		doit(i,0);
	}
	int ans = 0;
	rep(i,M) rep(t,2) if(done[i][t]) ans++;
	cout<<ans<<endl;

	int ans2 = 0;
	rep(i,M){
		int n = e2paths[i].size();
		chmin(n,2);
		ans2 += n;
	}
	assert(ans == ans2);
	rep(i,Q){
		if(dir[i]==0) cout<<X[i]+1<<" "<<Y[i]+1<<endl;
		else cout<<Y[i]+1<<" "<<X[i]+1<<endl;
	}
}