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 <cctype>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

namespace zyt
{
	template<typename T>
	inline bool read(T &x)
	{
		char c;
		bool f = false;
		x = 0;
		do
			c = getchar();
		while (c != EOF && c != '-' && !isdigit(c));
		if (c == EOF)
			return false;
		if (c == '-')
			f = true, c = getchar();
		do
			x = x * 10 + c - '0', c = getchar();
		while (isdigit(c));
		if (f)
			x = -x;
		return true;
	}
	template<typename T>
	inline void write(T x)
	{
		static char buf[20];
		char *pos = buf;
		if (x < 0)
			putchar('-'), x = -x;
		do
			*pos++ = x % 10 + '0';
		while (x /= 10);
		while (pos > buf)
			putchar(*--pos);
	}
	typedef pair<int, int> pii;
	const int N = 2e3 + 10;
	vector<int> v[N], g[N];
	int dep[N], n, m, fa[N], deg[N], p[N << 1], f[N << 1];
	pii arr[N << 1], bck[N << 1];
	bool tag[N << 1];
	queue<int> q;
	int find(const int u)
	{
		return !p[u] ? u : p[u] = find(p[u]);
	}
	void dfs(const int u, const int f)
	{
		dep[u] = dep[f] + 1;
		fa[u] = f;
		for (auto v : g[u])
		{
			if (v == f)
				continue;
			++deg[u];
			dfs(v, u);
		}
	}
	namespace LCA
	{
		const int B = 15;
		int fa[B][N];
		void dfs(const int u, const int f)
		{
			fa[0][u] = f;
			for (int i = 1; i < B; i++)
				fa[i][u] = fa[i - 1][fa[i - 1][u]];
			for (auto v : g[u])
			{
				if (v == f)
					continue;
				dfs(v, u);
			}
		}
		int lca(int a, int b)
		{
			if (dep[a] < dep[b])
				swap(a, b);
			for (int i = B - 1; i >= 0; i--)
				if (dep[fa[i][a]] >= dep[b])
					a = fa[i][a];
			if (a == b)
				return a;
			for (int i = B - 1; i >= 0; i--)
				if (fa[i][a] != fa[i][b])
					a = fa[i][a], b = fa[i][b];
			return fa[0][a];
		}
		int dis(const int a, const int b)
		{
			return dep[a] + dep[b] - dep[lca(a, b)] * 2;
		}
	}
	bool check(const int u, const int a, const int b)
	{
		using LCA::dis;
		return dis(a, u) + dis(b, u) == dis(a, b);
	}
	int work()
	{
		read(n), read(m);
		for (int i = 1; i < n; i++)
		{
			int u, v;
			read(u), read(v);
			g[u].push_back(v);
			g[v].push_back(u);
		}
		dfs(1, 0);
		LCA::dfs(1, 0);
		for (int i = 1; i <= n; i++)
			if (!deg[i])
				q.push(i);
		for (int i = 1; i <= m; i++)
		{
			read(arr[i].first), read(arr[i].second);
			bck[i] = arr[i];
			int a = arr[i].first, b = arr[i].second;
			if (dep[a] < dep[b])
				swap(a, b);
			while (dep[a] > dep[b])
				v[a].push_back(i), a = fa[a];
			while (a != b)
			{
				v[a].push_back(i), v[b].push_back(i);
				a = fa[a], b = fa[b];
			}
		}
		int cnt = m, ans = 0;
		for (int i = 2; i <= n; i++)
			ans += min(2, int(v[i].size()));
		while (q.size() && q.front() != 1)
		{
			static bool tg[N << 1];
			int u = q.front();
			q.pop();
			if (!fa[u])
				break;
			static int num[N << 1];
			vector<int> tmp;
			for (auto i : v[u])
				++num[find(i)];
			for (auto i : v[u])
				if (!--num[find(i)] && arr[find(i)].first != arr[find(i)].second 
					&& check(u, arr[find(i)].first, arr[find(i)].second))
				{
					tmp.push_back(find(i));
					if (arr[find(i)].first != u)
						swap(arr[find(i)].first, arr[find(i)].second), tg[find(i)] = 1;
				}
			if (tmp.size() == 1)
				arr[tmp[0]].first = fa[u];
			else if (tmp.size() > 1)
			{
				p[tmp[0]] = p[tmp[1]] = f[tmp[0]] = f[tmp[1]] = ++cnt;
				if (!tg[tmp[0]])
					tag[tmp[0]] = 1;
				if (tg[tmp[1]])
					tag[tmp[1]] = 1;
				arr[cnt] = pii(arr[tmp[0]].second, arr[tmp[1]].second);
				for (int i = 2; i < tmp.size(); i++)
					arr[tmp[i]].first = fa[u];
			}
			for (auto i : tmp)
				if (tg[i])
					swap(arr[i].first, arr[i].second), tg[i] = false;
			if (!--deg[fa[u]])
				q.push(fa[u]);
		}
		for (int i = cnt; i > 0; i--)
			tag[i] ^= tag[f[i]];
		write(ans), putchar('\n');
		for (int i = 1; i <= m; i++)
			if (tag[i])
				printf("%d %d\n", bck[i].second, bck[i].first);
			else
				printf("%d %d\n", bck[i].first, bck[i].second);
		return 0;
	}
}
int main()
{
	return zyt::work();
}