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;
const int N=500005;
typedef pair<int,int> pii;
#define mk make_pair
struct Edge{
    int from,to,flag;
}E[N];
int n,m;
vector<int> v[N];
vector<pii> G[N];

int deg[N],fa[N],dep[N],f[N][20];
void dfs(int u){
    deg[u]=0;
    for(int i=0;i<(int)v[u].size();i++){
        int to=v[u][i]; if(to==fa[u]) continue;
        deg[u]++; fa[to]=u; dep[to]=dep[u]+1;
        f[to][0]=u; for(int j=1;j<20;j++) f[to][j]=f[f[to][j-1]][j-1]; 
        dfs(to);
    }
}

int LCA(int x,int y){
    if(dep[x]<dep[y]) swap(x,y);
    for(int i=19;i>=0;i--) if(dep[f[x][i]]>=dep[y]) x=f[x][i];
    if(x==y) return x;
    for(int i=19;i>=0;i--) if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
    return f[x][0];
}

void init(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n-1;i++){
        int x,y; scanf("%d%d",&x,&y);
        v[x].push_back(y);
        v[y].push_back(x);
    }
    for(int i=1;i<=m;i++){
        scanf("%d%d",&E[i].from,&E[i].to); 
        E[i].flag=0;
    }
    dep[1]=1; dfs(1);
}

int ans=0,F[N][2];
void calc(){
    for(int i=1;i<=m;i++){
        int x=E[i].from,y=E[i].to,lca=LCA(x,y);
        while(x!=lca){
            F[x][0]=1; x=fa[x];
        }
        while(y!=lca){
            F[y][1]=1; y=fa[y];
        }
    }
    for(int i=1;i<=n;i++) ans+=F[i][0]+F[i][1];
}

int bl[N],rev[N];
int tot,vis[N];
queue<int> q;
int son[N][2];
void dfs2(int u){
    bl[u]=1;
    if(u<=m) {E[u].flag=rev[u]; return;}
    if(son[u][0]) rev[son[u][0]]=rev[u], dfs2(son[u][0]);
    if(son[u][1]) rev[son[u][1]]=rev[u]^1, dfs2(son[u][1]);
}
void solve(){
    for(int i=1;i<=m;i++){
        G[E[i].from].push_back(mk(E[i].to,i));
        G[E[i].to].push_back(mk(E[i].from,i));
    } tot=m;
    for(int i=1;i<=n;i++) if(!deg[i]) q.push(i);
    while(!q.empty()){
        int now=q.front(); q.pop(); vis[now]=1;
        int from=-1,preid=-1;
        for(int i=0;i<(int)G[now].size();i++){
            int to=G[now][i].first,id=G[now][i].second;
            if(vis[to]) continue;
            if(from==0) {
                if(fa[now]!=to){
                    tot++; son[tot][0]=id;
                    if(E[id].from!=now)
                    {
                        swap(E[id].from,E[id].to);
                        swap(son[id][0],son[id][1]);
                    }
                    E[tot].from=fa[now]; E[tot].to=E[id].to;
                    G[E[tot].from].push_back(mk(E[tot].to,tot));
                    G[E[tot].to].push_back(mk(E[tot].from,tot));
                }
            }
            else if(from==-1) from=to,preid=id;
            else{//preid->nowid
                if(E[preid].to!=now) 
                {
                    swap(E[preid].from,E[preid].to);
                    swap(son[preid][0],son[preid][1]);
                }
                if(E[id].to!=now) 
                {
                    swap(E[id].from,E[id].to);
                    swap(son[id][0],son[id][1]);
                }
                tot++; son[tot][0]=preid; son[tot][1]=id;
                E[tot].from=E[preid].from, E[tot].to=E[id].from;
                G[E[tot].from].push_back(mk(E[tot].to,tot));
                G[E[tot].to].push_back(mk(E[tot].from,tot));
                from=0; preid=-1;
            }
        }
        if(preid!=-1&&fa[now]!=from){
            if(E[preid].from!=now) 
            {
                swap(E[preid].from,E[preid].to);
                swap(son[preid][0],son[preid][1]);
            }
            tot++; son[tot][0]=preid;
            E[tot].from=fa[now]; E[tot].to=E[preid].to;
            G[E[tot].from].push_back(mk(E[tot].to,tot));
            G[E[tot].to].push_back(mk(E[tot].from,tot));
        }
        G[now].clear(); deg[fa[now]]--;
        if(!deg[fa[now]]) q.push(fa[now]);
    }
    for(int i=tot;i>=m+1;i--){
        if(!bl[i]) dfs2(i);
    }
    for(int i=1;i<=m;i++){
        if(E[i].flag) swap(E[i].from,E[i].to);
    }
    calc(); printf("%d\n",ans);
    for(int i=1;i<=m;i++) printf("%d %d\n",E[i].from,E[i].to);
}

int main(){
    init(); solve();
    return 0;
}