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;
 
#define REP(i, n) for(int i = 0; i < n; i++)
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define ST first
#define ND second
 
ostream& operator<<(ostream &out, string str) {
	for(char c : str) out << c;
	return out;
}
 
template<class L, class R> ostream& operator<<(ostream &out, pair<L, R> p) {
	return out << "(" << p.ST << ", " << p.ND << ")";
}

template<class T> auto operator<<(ostream &out, T &&x) -> decltype(x.begin(), out) {
	out << '{';
	for(auto &e : x)
        	out << e << (&e == &*--x.end() ? "" : ", ");
	return out << '}';
}

template<class... Args> void dump(Args&&... args) {
	((cerr << args << ";  "), ...);
}
 
#ifdef DEBUG
#  define debug(x...) cerr << "[" #x "]: ", dump(x), cerr << "\n"
#else
#  define debug(...) false
#endif
 
template<class T> int size(T && a) { return (int) a.size(); }
 
using LL = long long;
using PII = pair<int, int>;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int n, m;
	cin >> n >> m;

	vector<vector<int>> adj(n);
	REP(i, n - 1) {
		int a, b;
		cin >> a >> b;
		adj[a - 1].emplace_back(b - 1);
		adj[b - 1].emplace_back(a - 1);
	}

	vector<int> par(n), dep(n), sum(n);
	function<void(int, int)> dfs = [&](int v, int p) {
		par[v] = p;
		for(int u : adj[v]) {
			if(u != p) {
				dep[u] = dep[v] + 1;
				dfs(u, v);
			}
		}
	};
	dfs(0, -1);

	auto add_path = [&](int a, int b) {
		while(a != b) {
			if(dep[a] < dep[b])
				swap(a, b);
			sum[a]++;
			a = par[a];
		}
	};

	vector<vector<PII>> edges(n);
	vector<PII> ans;
	auto add_edge = [&](int u, int v) {
		edges[u].emplace_back(v, size(ans));
		edges[v].emplace_back(u, size(ans));
		ans.emplace_back(-1, -1);
	};

	REP(i, m) {
		int a, b;
		cin >> a >> b;
		a--, b--;
		add_path(a, b);
		add_edge(a, b);
	}

	REP(i, n)
		if(sum[i] % 2)
			add_edge(i, par[i]);

	vector<int> ptr(n);
	function<void(int)> get_cycle = [&](int v) {
		while(ptr[v] < size(edges[v])) {
			auto &[u, id] = edges[v][ptr[v]++];
			if(ans[id] == PII(-1, -1)) {
				ans[id] = {v, u};
				get_cycle(u);
			}
		}
	};
	REP(i, n) get_cycle(i);

	int s = 0;
	for(int &f : sum)
		s += min(f, 2);

	cout << s << "\n";
	REP(i, m) {
		auto &[u, v] = ans[i];
		cout << u + 1 << " " << v + 1 << "\n";
	}
}