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>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define sz(a) int(a.size())
#define clr(a) memset(a,0,sizeof(a))
#define all(a) a.begin(),a.end()
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,int> pli;
const int inf=1e9;
const ll Inf=1e18;
const int N=2e3+10;
const int mod=0;
int gi() {
    int x=0,o=1;char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
    if(ch=='-') o=-1,ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x*o;
}
template<typename T> bool chkmax(T &a,T b) { return a<b?a=b,1:0; };
template<typename T> bool chkmin(T &a,T b) { return a>b?a=b,1:0; };
int add(int a,int b) { return a+b>=mod?a+b-mod:a+b; }
int sub(int a,int b) { return a-b<0?a-b+mod:a-b; }
void inc(int &a,int b) { a=(a+b>=mod?a+b-mod:a+b); }
void dec(int &a,int b) { a=(a-b<0?a-b+mod:a-b); }
int n,m,fa[N],faw[N],dep[N],ans=0;
vector<int> E[N],du;
vector<pii> path;
void dfs(int u,int ff,int d) {
    fa[u]=ff,dep[u]=d;
    for(int v:E[u]) if(v!=ff) dfs(v,u,d+1);
}
void modify(int u,int v) {
    if(dep[u]<dep[v]) swap(u,v);
    while(dep[u]>dep[v]) ++faw[u],u=fa[u];
    while(u!=v) ++faw[u],++faw[v],u=fa[u],v=fa[v];
}
vector<pii> solve(vector<pii> path,vector<int> du) {
    if(path.empty()) return path;
    int u=1,v=0;
    while(du[u]!=1) ++u;
    for(int x:E[u]) if(du[x]) { v=x;break; }
    --du[u],--du[v];
    vector<pii> now,nxt;
    vector<int> bel;
    for(pii x:path) {
        if(x.se==u) swap(x.fi,x.se);
        if(x.fi==u) now.pb(x),bel.pb(0);
        else nxt.pb(x),bel.pb(1);
    }
    if(now.empty()) return solve(path,du);
    vector<int> ref(sz(now));
    fill(all(ref),-1);
    for(int i=0;i+1<sz(now);i+=2) {
        pii &x=now[i],y=now[i+1];
        if(x.se!=y.se) nxt.pb(mp(x.se,y.se)),ref[i]=ref[i+1]=sz(nxt)-1;
        else swap(x.fi,x.se);
    }
    if(sz(now)&1) {
        pii x=now.back();
        if(x.se!=v) nxt.pb(mp(v,x.se)),ref[sz(now)-1]=sz(nxt)-1;
    }
    nxt=solve(nxt,du);
    path.clear();int p1=0,p2=0;
    for(int x:bel) {
        if(!x) {
            if(~ref[p1]&&nxt[ref[p1]].fi!=now[p1].fi&&nxt[ref[p1]].se!=now[p1].se) swap(now[p1].fi,now[p1].se);
            path.pb(now[p1++]);
        }
        else path.pb(nxt[p2++]);
    }
    return path;
}
int main() {
    n=gi(),m=gi();du.resize(n+1);
    for(int i=1,u,v;i<n;i++) u=gi(),v=gi(),E[u].pb(v),E[v].pb(u),++du[u],++du[v];
    dfs(1,0,0);
    for(int i=1,u,v;i<=m;i++) u=gi(),v=gi(),modify(u,v),path.pb(mp(u,v));
    for(int i=2;i<=n;i++) ans+=min(2,faw[i]);
    path=solve(path,du);
    printf("%d\n",ans);
    for(pii x:path) printf("%d %d\n",x.fi,x.se);
    return 0;
}