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 <algorithm>
// #include <cstdlib>
#include <cstring>
#include <cstdio>
#include <string>
#include <queue>
#include <cmath>
#include <set>
#include <map>
#include <bitset>
using namespace std;
typedef long long LL;
typedef double db;
const int oo=2139063143;
const int N=10010;
const int P=1000000007;
const db eps=1e-7;
#define pritnf printf
//char buf[1<<22],*p1=buf,*p2=buf,obuf[1<<22],*O=obuf;
//#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
template <typename T>
inline void sc (T &x)
{
    x=0; static int p; p=1; static char c; c=getchar();
    while (!isdigit(c)) { if (c=='-') p=-1; c=getchar(); }
    while ( isdigit(c)) { x=(x<<1)+(x<<3)+(c-48); c=getchar(); }
    x*=p;
}
template <typename T>
inline void print (T x)
{
    if (x< 0) putchar('-'),x=-x;
    if (x>=10) print(x/10);
    putchar(x%10+'0');
}
template <typename T>
inline void pr (T x) { print(x),putchar('\n'); }
template <typename T1,typename T2>
void chkmax (T1 &A,T2 B) { A=A>=B?A:B; }
template <typename T1,typename T2>
void chkmin (T1 &A,T2 B) { A=A<=B?A:B; }
int n,m;
struct LY { int x,y,nx; bool op; }a[N]; int k=0;
#define pb push_back
#define pii pair<int,int>
#define se second
#define fi first
#define mp make_pair
vector <pii> G[N];
set <int> s[N];
int deg[N];
int st[N],z=0;
void del (int i) { s[a[i].x].erase (i),s[a[i].y].erase (i); }
void add (int i) { s[a[i].x].insert (i),s[a[i].y].insert (i); }
void solve ()
{
	queue <int> q;
	for (int i=1; i<=n; i++)
		if (deg[i]==1) q.push (i);
	while (q.size ())
	{
		int u=q.front (); q.pop ();
		z=0;
		bool fg=0;
		for (set <int> :: iterator it=s[u].begin (); it!=s[u].end (); it++)
		{
			int i=*it;
			if (a[i].x==a[i].y) { a[i].op=1,fg^=1; if (fg) swap (a[i].x,a[i].y); continue; }
			st[++z]=i;
		}
		while (z>=2)
		{
			int i=st[z],j=st[z-1]; del (i),del (j);
			if (a[i].x==u) swap (a[i].x,a[i].y);
			if (a[j].x==u) swap (a[j].x,a[j].y);
			if (a[i].x==a[j].x&&a[i].y==a[j].y) { swap (a[j].x,a[j].y),a[i].op=a[j].op=1; z-=2; continue; }
			a[++k].x=a[i].x,a[k].y=a[j].x,add (k);
			a[i].nx=a[j].nx=k;
			z-=2;
		}
		if (z)
		{
			for (pii x:G[u]) if (deg[x.fi]-1>=1)
			{
				int v=x.fi,i=st[z--]; del (i);
				a[++k]=a[i]; a[i].nx=k;
				((a[i].x==u)?a[k].x:a[k].y)=v;
				add (k);
			}
		}
		for (pii x:G[u])
			if (--deg[x.fi]==1) q.push (x.fi);
	}
}
int ans[N]; bool fg=0;
void dfs (int u,int fa,int aim)
{
	if (u==aim)
	{
		while (z) ++ans[st[z--]];
		fg=1;
	}
	if (fg) return ;
	for (pii x:G[u]) if (x.fi!=fa)
		st[++z]=x.se,dfs (x.fi,u,aim),--z;
}
int main ()
{
    // freopen (".in","r",stdin);
    // freopen (".out","w",stdout);
	sc(n),sc(m);
	for (int i=1; i< n; i++)
	{
		int x,y; sc(x),sc(y);
		G[x].pb (mp(y,i)),G[y].pb (mp(x,i));
		++deg[x],++deg[y];
	}
	for (int i=1; i<=m; i++)
	{
		int x,y; sc(x),sc(y); a[++k].x=x,a[k].y=y;
		add (i),fg=0,z=0,dfs (x,0,y);
	}
	solve ();
	for (int i=k; i>=1; i--) if (!a[i].op)
	{
		int j=a[i].nx;
		if ((a[i].x==a[j].x)+(a[i].y==a[j].y)==0) swap (a[i].x,a[i].y);
	}
	for (int i=1; i< n; i++)
		ans[0]+=min (ans[i],2);
	pr(ans[0]);
	for (int i=1; i<=m; i++)
		printf ("%d %d\n",a[i].x,a[i].y);

    return 0;
}