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;
#define ll long long
#define REP(i,a,b) for(int i=(a),_end_=(b);i<=_end_;i++)
#define DREP(i,a,b) for(int i=(a),_end_=(b);i>=_end_;i--)
#define EREP(i,u) for(int i=start[u];i;i=e[i].next)
#define fi first
#define se second
#define mkr(a,b) make_pair(a,b)
#define SZ(A) ((int)A.size())
template<class T>inline void chkmin(T &a,T b){ if(a>b)a=b;}
template<class T>inline void chkmax(T &a,T b){ if(a<b)a=b;}
inline void myassert(bool a,string s){ if(!a)cerr<<s<<endl,exit(0);}
inline int read()
{
	int s=0,f=1;char ch=getchar();
	while(!isdigit(ch) && ch!='-')ch=getchar();
	if(ch=='-')ch=getchar(),f=-1;
	while(isdigit(ch))s=s*10+ch-'0',ch=getchar();
	return ~f?s:-s;
}

const int maxn=2e3+20;

vector<int>ed[maxn];

struct Edge {
	int u,v;
};
Edge OE[maxn],E[maxn<<1],T[maxn];
int ff[maxn<<1],ffw[maxn<<1];

int n,m,mtot;
int cf[maxn];
int ans=0;

int deep[maxn],fa[maxn];

void dfs(int u)
{
	for(int v:ed[u])
	{
		if(v==fa[u])continue;
		fa[v]=u;
		deep[v]=deep[u]+1;
		dfs(v);
	}
}

inline int lca(int u,int v)
{
	while(u!=v)
	{
		if(deep[u]>deep[v])swap(u,v);
		v=fa[v];
	}
	return u;
}

inline void take_cover0(int u,int v)
{
	int t=lca(u,v);
	while(u!=t)cf[u]++,u=fa[u];
	while(v!=t)cf[v]++,v=fa[v];
}

inline void init()
{
	n=read();mtot=m=read();
	REP(i,1,n-1)
	{
	 	int u=read(),v=read();
 	  	ed[u].push_back(v);
	 	ed[v].push_back(u);
		T[i]=(Edge){u,v};
	}
	REP(i,1,m)
	{
		int u=read(),v=read();
		OE[i]=E[i]=(Edge){u,v};
	}
	dfs(1);
	REP(i,1,m)take_cover0(E[i].u,E[i].v);
	REP(i,1,n)ans+=min(cf[i],2);
}

void solve(vector<int>tree,vector<int>edge)
{
	if(SZ(tree)==0)return;
	if(SZ(edge)<=1)
	{
		for(int i:edge)ffw[i]=0;
		return;
	}
	static int rd[maxn];
	memset(rd,0,sizeof(int)*(n+1));
	for(int i:tree)rd[T[i].u]++,rd[T[i].v]++;
	int U=0,V=0;
	REP(i,1,n)if(rd[i]==1){ U=i; break;}
	int j=0;
	vector<int>nedge,ntree;
	for(int i:tree)
		if(T[i].u==U || T[i].v==U)V=T[i].u^T[i].v^U;
		else ntree.push_back(i);

	vector<int>vis(2*m+1);
	
	for(int i:edge)
	{
		if(E[i].u==U || E[i].v==U)
		{
			if(j)
			{
				int a=E[j].u^E[j].v^U,b=E[i].u^E[i].v^U;
				if(a!=b)
				{
					ff[i]=ff[j]=++mtot; nedge.push_back(mtot);
					E[mtot]=(Edge){a,b};
					ffw[j]=(E[j].u!=a);
					ffw[i]=(E[i].v!=b);
					vis[i]=vis[j]=1;
				}else ffw[i]=1,ffw[j]=E[j].u != E[i].u;
				j=0;
			}else j=i;
		}else nedge.push_back(i);
	}
	if(j)
	{
		if(E[j].u==U)E[j].u=V;
		if(E[j].v==U)E[j].v=V;
		if(E[j].u!=E[j].v)nedge.push_back(j);
	}
	solve(ntree,nedge);
	for(int i:edge)if(vis[i])ffw[i]^=ffw[ff[i]];
}

inline void doing()
{
	printf("%d\n",ans);
	vector<int>tree,edge;
	REP(i,1,n-1)tree.push_back(i);
	REP(i,1,m)edge.push_back(i);
	solve(tree,edge);
	REP(i,1,m)
	{
		if(ffw[i])swap(OE[i].u,OE[i].v);
		printf("%d %d\n",OE[i].u,OE[i].v);
	}
}

int main()
{
	init();
	doing();
	return 0;
}