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 <cstdio>
#include <cstring>
#include <algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
#define rep(i,a) for(int i=lst[a];i;i=nxt[i])
#define mp(a,b) make_pair(a,b)
using namespace std;

typedef pair<int,int> pii;
#define fi first 
#define se second 

int read() {
	char ch;
	for(ch=getchar();ch<'0'||ch>'9';ch=getchar());
	int x=ch-'0';
	for(ch=getchar();ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x;
}

const int N=2e3+5;

int t[N<<1],nxt[N<<1],lst[N],l;
void add(int x,int y) {t[++l]=y;nxt[l]=lst[x];lst[x]=l;}

int n,m,deg[N],fa[N][11],dep[N],c[N],u[N],v[N],p[N];
bool col[N],ban[N];
pii now[N];

void dfs(int x,int y) {
	dep[x]=dep[y]+1;fa[x][0]=y;
	rep(i,x) if (t[i]!=y) dfs(t[i],x);
}

int lca(int x,int y) {
	if (dep[x]<dep[y]) swap(x,y);
	fd(j,10,0) if (dep[fa[x][j]]>dep[y]) x=fa[x][j];
	x=dep[x]==dep[y]?x:fa[x][0];
	fd(j,10,0) if (fa[x][j]!=fa[y][j]) x=fa[x][j],y=fa[y][j];
	return x==y?x:fa[x][0];
}

void calc(int x,int y) {rep(i,x) if (t[i]!=y) calc(t[i],x),c[x]+=c[t[i]];}

int main() {
	n=read();m=read();
	fo(i,1,n-1) {
		int x=read(),y=read();
		add(x,y);add(y,x);
		deg[x]++;deg[y]++;
	}
	dfs(1,0);
	fo(j,1,10) fo(i,1,n) fa[i][j]=fa[fa[i][j-1]][j-1];
	fo(i,1,m) {
		u[i]=read(),v[i]=read();
		int z=lca(u[i],v[i]);
		c[u[i]]++;c[v[i]]++;c[z]-=2;
	}
	calc(1,0);
	fo(i,1,m) now[i]=mp(u[i],v[i]);
	int ans=0;
	fo(i,1,n) ans+=min(c[i],2);
	printf("%d\n",ans);
	fo(tim,1,n-1) {
		int x,y;
		fo(i,2,n) if (!ban[i]&&deg[i]==1) {x=i;break;}
		rep(j,x) if (!ban[t[j]]) y=t[j];
		ban[x]=1;deg[y]--;
		int p1=0,p2=0;
		fo(i,1,m)
			if ((now[i].fi==x)^(now[i].se==x)) {
				if (!p1) p1=i;
				else if (!p2) p2=i;
			}
		if (!p1) continue;
		if (!p2) {
			if (now[p1].fi==x) now[p1].fi=y;
			else now[p1].se=y;
			continue;
		}
		if (now[p1].fi==x) {
			if (now[p2].fi==x) {
				now[p1].fi=now[p2].se;
				col[p2]^=1;
			} else now[p1].fi=now[p2].fi;
		} else {
			if (now[p2].se==x) {
				now[p1].se=now[p2].fi;
				col[p2]^=1;
			} else now[p1].se=now[p2].se;
		}

		p[p2]=p1;now[p2].fi=now[p2].se;
		fo(i,1,m) {
			if (now[i].fi==x) now[i].fi=y;
			if (now[i].se==x) now[i].se=y;
		}
	}
	fo(i,1,m) if (p[i]) col[i]^=col[p[i]];
	fo(i,1,m) {
		if (col[i]) swap(u[i],v[i]);
		printf("%d %d\n",u[i],v[i]);
	}
	return 0;
}