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;
inline int gi()
{
	char c=getchar(); int x=0;
	for(;c<'0'||c>'9';c=getchar());
	for(;c>='0'&&c<='9';c=getchar())x=(x<<1)+(x<<3)+c-'0';
	return x;
}
typedef pair<int,int> pr;
const int N=2019;
vector<int> e[N];
struct node
{
	int u,v;
}; vector<node> a;
int n,m,u[N],v[N],d[N],dep[N],fa[N],cov[N],ans;
void dfs(int u)
{
	for(auto v:e[u]) if(v!=fa[u])
		++d[u],dep[v]=dep[u]+1,fa[v]=u,dfs(v);
}
void apply(int u, int v)
{
	if(dep[u]<dep[v]) swap(u,v);
	for(;dep[u]!=dep[v];u=fa[u]) ++cov[u];
	for(;u!=v;u=fa[u],v=fa[v]) ++cov[u],++cov[v];
}
queue<int> q;
bool flag;
vector<int> solve(vector<node> a)
{
	if(!a.size()||q.empty())
	{
		vector<int> tmp;
		tmp.resize(a.size());
		return tmp;
	}
	int u=q.front(); q.pop();
	for(auto v:e[u]) if(!(--d[v])) q.push(v);
	vector<int> b,c,g;
	vector<node> d;
	c.resize(a.size());
	for(int i=0;i<a.size();++i) if((a[i].u==u||a[i].v==u)&&a[i].u!=a[i].v) b.push_back(i);
	for(auto x:b) if(a[x].u!=u) swap(a[x].u,a[x].v),c[x]^=1;
	for(int i=1;i<b.size();i+=2) d.push_back((node){a[b[i-1]].v,a[b[i]].v}); 
	for(int i=0;i<a.size();++i) if(a[i].u!=u&&a[i].v!=u) d.push_back(a[i]);
	if(b.size()&1&&a[b.back()].u!=a[b.back()].v)
		d.push_back((node){fa[a[b.back()].u],a[b.back()].v});
	g=solve(d); int j=0;
	for(int i=1;i<b.size();i+=2,++j) c[b[i-1]]^=(g[j]^1),c[b[i]]^=g[j];
	for(int i=0;i<a.size();++i) if(a[i].u!=u&&a[i].v!=u) c[i]=g[j++];
	if(b.size()&1&&a[b.back()].u!=a[b.back()].v) c[b.back()]^=g.back();
	return c;
}
int main()
{
	n=gi(),m=gi();
	for(int i=1;i<n;++i)
	{
		int u=gi(),v=gi();
		e[u].push_back(v),e[v].push_back(u);
	}
	dfs(1);
	for(int i=1;i<=m;++i)
	{
		u[i]=gi(),v[i]=gi();
		apply(u[i],v[i]);
		a.push_back((node){u[i],v[i]});
	}
	for(int i=2;i<=n;++i) ans+=min(2,cov[i]);
	for(int i=1;i<=n;++i) if(!d[i]) q.push(i);
	vector<int> b=solve(a);
	printf("%d\n",ans);
	for(int i=1;i<=m;++i)
	{
		if(b[i-1]) swap(u[i],v[i]);
		printf("%d %d\n",u[i],v[i]);
	}
}