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

int n,m;

struct edge{int to,nxt;}E[4050];
int H[2050],tot;
void add_edge(int a,int b){
	E[++tot]=(edge){b,H[a]},H[a]=tot;
	E[++tot]=(edge){a,H[b]},H[b]=tot;
}

int Lson[8000050],Rson[8000050],ptot;
std::pair<int,int> paths[8000050],res[2050];
bool removed[8000050];

int dep[2050],Fa[2050],accu[2050],lst[2050],lsttop;
std::vector<int> Id[2050],tmp;
std::vector<int> roots;

void pre(int now,int fa){
	lst[++lsttop]=now;
	dep[now]=dep[fa]+1,Fa[now]=fa;
	for (int i=H[now];i;i=E[i].nxt)
		if (E[i].to!=fa) pre(E[i].to,now);
}
int LCA(int x,int y){
	while (dep[x]>dep[y]) x=Fa[x];
	while (dep[y]>dep[x]) y=Fa[y];
	while (x!=y) x=Fa[x],y=Fa[y];
	return x;
}

void solve(int now,int fa){
	for (int i=H[now];i;i=E[i].nxt)
		if (E[i].to!=fa) solve(E[i].to,now);
	tmp.clear();
	for (std::vector<int>::iterator it=Id[now].begin();it!=Id[now].end();++it)
		if (!removed[*it]){
			if (paths[*it].first==paths[*it].second) roots.push_back(*it),removed[*it]=true;
			else tmp.push_back(*it);
		}
	Id[now]=tmp;
	while (Id[now].size()>=2){
		int nxt=++ptot,x,y;
		x=paths[Id[now].back()].first==now?paths[Id[now].back()].second:paths[Id[now].back()].first;
		Lson[nxt]=Id[now].back();
		removed[Id[now].back()]=true;
		Id[now].pop_back();
		y=paths[Id[now].back()].first==now?paths[Id[now].back()].second:paths[Id[now].back()].first;
		Rson[nxt]=Id[now].back();
		removed[Id[now].back()]=true;
		Id[now].pop_back();

		paths[nxt]=std::make_pair(x,y);

		Id[x].push_back(nxt);
		Id[y].push_back(nxt);
	}
	if (Id[now].size()){
		int nxt=++ptot,x;
		x=paths[Id[now].back()].first==now?paths[Id[now].back()].second:paths[Id[now].back()].first;
		Lson[nxt]=Id[now].back();
		removed[Id[now].back()]=true;
		paths[nxt]=std::make_pair(x,Fa[now]);
		Lson[nxt]=Id[now].back();
		Id[now].pop_back();

		Id[Fa[now]].push_back(nxt);
		if (x!=Fa[now]) Id[x].push_back(nxt);
	}
}

void gett(int now,bool way){
	if (!Lson[now]){
		if (way) std::swap(paths[now].first,paths[now].second);
		res[now]=paths[now];
	}
	else if (!Rson[now]){
		if (paths[now].first==paths[Lson[now]].first||paths[now].second==paths[Lson[now]].second) gett(Lson[now],way);
		else gett(Lson[now],!way);
	}
	else{
		if (paths[now].first==paths[Lson[now]].first) gett(Lson[now],way);
		else gett(Lson[now],!way);
		if (paths[now].second==paths[Rson[now]].first) gett(Rson[now],!way);
		else gett(Rson[now],way);
	}
}

int ans;

int main(){
	scanf("%d%d",&n,&m);
	for (int i=1,x,y;i<n;i++) scanf("%d%d",&x,&y),add_edge(x,y);
	pre(1,0);
	for (int i=1,x,y;i<=m;i++){
		scanf("%d%d",&x,&y),paths[i]=std::make_pair(x,y);
		Id[x].push_back(i),Id[y].push_back(i);
		accu[x]++,accu[y]++,accu[LCA(x,y)]-=2;
	}
	for (int i=n;i;i--) accu[Fa[lst[i]]]+=accu[lst[i]];
	for (int i=1;i<=n;i++) ans+=std::min(accu[i],2);
	printf("%d\n",ans);
	ptot=m;

	solve(1,0);
	for (std::vector<int>::iterator it=roots.begin();it!=roots.end();++it) gett(*it,false);
	for (int i=1;i<=m;i++) printf("%d %d\n",res[i].first,res[i].second);
}