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<cstring>
#include<vector>
#define x first
#define y second

namespace oo
{
	typedef std::pair<int,int> pii;

	const int N=2010;

	int begin[N],next[N*2],to[N*2];

	pii s[N];

	int n,m,e;

	int fa[N],vis[N],cnt[N];
	void predfs(int p=1,int h=0)
	{
		fa[p]=h;
		for(int i=begin[p],q;i;i=next[i])
			if((q=to[i])!=h)predfs(q,p);
	}
	int calculate()
	{
		predfs();
		for(int i=1;i<=m;i++)
		{
			int u=s[i].x,v=s[i].y;
			memset(vis,0,sizeof(vis));
			while(u!=1)vis[u]^=1,u=fa[u];
			while(v!=1)vis[v]^=1,v=fa[v];
			for(int j=2;j<=n;j++)cnt[j]+=vis[j];
		}
		int ret=0;
		for(int i=2;i<=n;i++)ret+=std::min(2,cnt[i]);
		return ret;
	}

	void add(int x,int y,bool k=1)
	{
		to[++e]=y;
		next[e]=begin[x];
		begin[x]=e;
		if(k)add(y,x,0);
	}
	void initialize()
	{
		scanf("%d%d",&n,&m);
		for(int i=1,u,v;i<n;i++)
			scanf("%d%d",&u,&v),add(u,v);
		for(int i=1;i<=m;i++)
			scanf("%d%d",&s[i].x,&s[i].y);
	}

	bool fucked[N];
	int f[N][N],g[N][N];

	inline void ins(int u,int v){f[u][v]++,f[v][u]++;}
	inline void del(int u,int v){f[u][v]--,f[v][u]--;}

	int find()
	{
		int ret=0;
		for(int p=1;p<=n;p++)
		{
			if(fucked[p])continue;

			int deg=0;
			for(int i=begin[p];i;i=next[i])
				if(!fucked[to[i]])deg++;
			if(deg==1)ret=p;
		}
		return ret;
	}
	int adj(int p)
	{
		int ret=0;
		for(int i=begin[p];i;i=next[i])
			if(!fucked[to[i]])ret=to[i];
		return ret;
	}

	void work()
	{
		int p=find();
		if(!p)return;

//		printf("work : %d\n",p);

		std::vector<int> seq;

		while(f[p][p]>0)del(p,p),g[p][p]++;
		for(int q=1;q<=n;q++)
			while(f[p][q]>0)
				del(p,q),seq.push_back(q);

		int spl=0,q=0;

		for(int i=0;i+1<(int)seq.size();i+=2)
		{
			del(p,seq[i]),del(p,seq[i+1]);
			ins(seq[i],seq[i+1]);
		}
		if(seq.size()%2!=0)
		{
			spl=seq.end()[-1],q=adj(p);
			del(p,spl),ins(q,spl);
		}

		fucked[p]=1,work();

		for(int i=0,u,v;i+1<(int)seq.size();i+=2)
		{
			u=seq[i],v=seq[i+1];
			if(!g[u][v])std::swap(u,v);

			g[u][v]--,g[u][p]++,g[p][v]++;
		}
		if(seq.size()%2!=0)
		{
			if(g[q][spl])g[q][spl]--,g[p][spl]++;
			else g[spl][q]--,g[spl][p]++;
		}
	}
	void solve()
	{
		initialize();

		for(int i=1;i<=m;i++)
			ins(s[i].x,s[i].y);

		work();

		printf("%d\n",calculate());

		for(int i=1;i<=m;i++)
		{
			if(!g[s[i].x][s[i].y])std::swap(s[i].x,s[i].y);

			printf("%d %d\n",s[i].x,s[i].y);

			g[s[i].x][s[i].y]--;
		}
	}
}

int main()
{
//	freopen("E.in","r",stdin);

	oo::solve();
	return 0;
}