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 signed long long ll;

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------

int N,M;
vector<int> E[2020];

int EE[2020][2],TE[2020][2];
set<int> VE[2020];
vector<int> EL[2020];
int dir[2020];
int cnt[2020][2020];

void shrink(int cur) {
	FORR(c,EL[cur]) dir[c%M] = c/M;
}

int dfs(int cur,int pre,int tar) {
	if(cur==tar) {
		cnt[pre][cur]++;
		return 1;
	}
	else {
		int ok=0;
		FORR(e,E[cur]) if(e!=pre) ok+=dfs(e,cur,tar);
		if(ok&&pre) cnt[pre][cur]++;
		return ok>=1;
	}
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,N-1) {
		cin>>x>>y;
		E[x].push_back(y);
		E[y].push_back(x);
	}
	
	dfs(1,1,0);
	FOR(i,M) {
		cin>>EE[i][0]>>EE[i][1];
		dfs(EE[i][0],0,EE[i][1]);
		TE[i][0]=EE[i][0];
		TE[i][1]=EE[i][1];
		VE[EE[i][0]].insert(i);
		VE[EE[i][1]].insert(i+M);
		EL[i].push_back(i);
	}
	
	
	int ret=0;
	for(y=1;y<=N;y++) for(x=1;x<y;x++) ret+=min(2,cnt[x][y]+cnt[y][x]);
	cout<<ret<<endl;
	
	while(true) {
		for(i=1;i<=N;i++) if(E[i].size()==1) break;
		if(i>N) break;
		int cur=i;
		vector<int> delcand;
		FORR(v,VE[cur]) if(v<M && VE[cur].count(v+M)) {
			delcand.push_back(v);
			shrink(v);
		}
		FORR(d,delcand) VE[cur].erase(d),VE[cur].erase(d+M);
		
		
		int p=E[cur][0];
		if(VE[cur].size()==1) {
			int l=*VE[cur].begin();
			TE[l%M][l/M]=p;
			VE[p].insert(l);
		}
		else if(VE[cur].size()>=2) {
			int a=*VE[cur].begin()%M;
			
			VE[TE[a][0]].erase(a);
			VE[TE[a][1]].erase(a+M);
			int b=*VE[cur].begin()%M;
			VE[TE[b][0]].erase(b);
			VE[TE[b][1]].erase(b+M);
			
			if(TE[a][0]==cur) {
				FORR(e,EL[a]) {
					if(e>=M) e-=M;
					else e+=M;
				}
				swap(TE[a][0],TE[a][1]);
			}
			if(TE[b][1]==cur) {
				FORR(e,EL[b]) {
					if(e>=M) e-=M;
					else e+=M;
				}
				swap(TE[b][0],TE[b][1]);
			}
			TE[a][1]=TE[b][1];
			FORR(e,EL[b]) EL[a].push_back(e);
			EL[b].clear();
			VE[TE[a][0]].insert(a);
			VE[TE[a][1]].insert(a+M);
			
			FORR(v,VE[cur]) {
				TE[v%M][v/M]=p;
				VE[p].insert(v);
			}
		}
		VE[cur].clear();
		E[p].erase(remove(ALL(E[p]),cur),E[p].end());
		E[cur].clear();
	}
	
	for(i=1;i<=N;i++) FORR(v,VE[i]) shrink(v);
	FOR(i,M) {
		if(dir[i]) cout<<EE[i][1]<<" "<<EE[i][0]<<endl;
		else cout<<EE[i][0]<<" "<<EE[i][1]<<endl;
	}
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	cout.tie(0); solve(); return 0;
}