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:
// This amazing code is by Eric Sunli Chen.
#include<bits/stdc++.h>
using namespace std;
template<typename T> bool get_int(T &x)
{
	char t=getchar();
	bool neg=false;
	x=0;
	for(; (t>'9'||t<'0')&&t!='-'&&t!=EOF; t=getchar());
	if(t=='-')neg=true,t=getchar();if(t==EOF)return false;
	for(; t<='9'&&t>='0'; t=getchar())x=x*10+t-'0';
	if(neg)x=-x;return true;
}
template<typename T> void print_int(T x)
{
	if(x<0)putchar('-'),x=-x;
	short a[20]= {},sz=0;
	while(x>0)a[sz++]=x%10,x/=10;
	if(sz==0)putchar('0');
	for(int i=sz-1; i>=0; i--)putchar('0'+a[i]);
}
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define get1(a) get_int(a)
#define get2(a,b) (get1(a)&&get1(b))
#define get3(a,b,c) (get1(a)&&get2(b,c))
#define printendl(a) print_int(a),puts("")
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int,int> pii;
const int inf=0x3f3f3f3f;
const LL Linf=1ll<<61;
const double pi=acos(-1.0);

const int maxn=2111;

int n,m,seq[maxn],fa[maxn],timer;
vector<int> g[maxn];

void dfs(int x,int f)
{
	fa[x]=f;seq[++timer]=x;
	for(auto v:g[x])if(v!=f)dfs(v,x);
}

vector<int> get_ans(vector<pii> es,int cur)
{
	vector<int> nw;nw.resize(es.size(),0);
	if(cur==1)return nw;
	int piv=seq[cur],val=-1;
//	printf("piv= %d\n",piv);
	
	vector<pii> n_es,tp;
	
	for(int i=0;i<(int)es.size();i++)
	{
		if(es[i].ff!=piv&&es[i].ss!=piv)
		{
			n_es.pb(es[i]);
			tp.pb(mp(i,-1));
			continue;
		}
		if(es[i].ff==piv)
		{
			swap(es[i].ff,es[i].ss);
			nw[i]=1;
		}
		if(es[i].ff==piv)continue;
		if(val==-1)val=i;
		else
		{
			n_es.pb(mp(es[val].ff,es[i].ff));
			tp.pb(mp(val,i));
			val=-1;
		}
	}
	if(val!=-1)
	{
		n_es.pb(mp(es[val].ff,fa[piv]));
		tp.pb(mp(val,-1));
	}
	vector<int> old=get_ans(n_es,cur-1);
	for(int i=0;i<(int)old.size();i++)
	{
		nw[tp[i].ff]^=old[i];
		if(tp[i].ss>=0)nw[tp[i].ss]^=old[i]^1;
	}
	return nw;
}

int main()
{
	get2(n,m);
	for(int i=1,u,v;i<n;i++)
	{
		get2(u,v);
		g[u].pb(v);
		g[v].pb(u);
	}
	vector<pii> es;
	for(int i=1,u,v;i<=m;i++)
	{
		get2(u,v);
		es.pb(mp(u,v));
	}
	dfs(1,0);
	vector<int> ans=get_ans(es,n);
	set<pii> st;
	for(int i=0;i<(int)es.size();i++)
	{
		if(ans[i])swap(es[i].ff,es[i].ss);
		timer=0;dfs(es[i].ff,0);
		int tmp=es[i].ss;
		while(tmp!=es[i].ff)
		{
			st.insert(mp(fa[tmp],tmp));
			tmp=fa[tmp];
		}
	}
	printf("%d\n",(int)st.size());
	for(int i=0;i<(int)es.size();i++)printf("%d %d\n",es[i].ff,es[i].ss);
	return 0;
}