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;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll MAX=2005;
const ll INF=0x3f3f3f3f;
const ll MOD=998244353;
int n,par[MAX],depth[MAX],m,cnt[MAX][MAX],fcnt[MAX][MAX],chk_ans2[MAX],ans;
vector<int> conn[MAX],walk[MAX],lotus[MAX][MAX];
vector<pii> ans2;
queue<pii> now_edge;
void build(int px,int x,int d){
    depth[x]=d; par[x]=px;
    for(int i=0;i<conn[x].size();i++) if(conn[x][i]!=px) build(x,conn[x][i],d+1);
}
void seq_push(int idx,int pt,int fin,int mode){
    if(pt!=fin&&mode) walk[idx].push_back(pt);
    if(pt!=fin) seq_push(idx,par[pt],fin,mode);
    if(!mode) walk[idx].push_back(pt);
}
int process(){
    if(now_edge.size()==0){
        for(int i=0;i<m;i++) if(chk_ans2[i]==0){
            chk_ans2[i]=1;
            for(int j=0;j<walk[i].size()-1;j++) {
                int t1=walk[i][j],t2=walk[i][j+1];
                fcnt[t1][t2]++;
                if(cnt[t1][t2]-fcnt[t1][t2]==1&&fcnt[t2][t1]==0) now_edge.push(make_pair(t2,t1));
            }
            return 1;
        }
        return 0;
    }
    pii tmp=now_edge.front();
    int a=tmp.first,b=tmp.second,i,rev=0;
    now_edge.pop();
    if(fcnt[a][b]==0){
        fcnt[a][b]++;
        for(int j=0;j<lotus[a][b].size();j++){
            if(chk_ans2[lotus[a][b][j]]==0) i=lotus[a][b][j];
        }
        chk_ans2[i]=1;
        for(int j=0;j<walk[i].size()-1;j++){
            if(a==walk[i][j+1]&&b==walk[i][j]) rev=1;
        }
        if(rev) swap(ans2[i].first,ans2[i].second);
        for(int j=0;j<walk[i].size()-1;j++) {
            int t1=walk[i][j],t2=walk[i][j+1];
            if(rev) swap(t1,t2);
            fcnt[t1][t2]++;
            if(cnt[t1][t2]-fcnt[t1][t2]==1&&fcnt[t2][t1]==0) now_edge.push(make_pair(t2,t1));
        }
    }
    return 1;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=0;i<n-1;i++){
        int t1,t2;
        scanf("%d%d",&t1,&t2);
        conn[t1].push_back(t2);
        conn[t2].push_back(t1);
    }
    build(1,1,0);
    for(int i=0;i<m;i++){
        int a,b,t1,t2;
        scanf("%d%d",&a,&b);
        t1=a,t2=b;
        if(depth[t1]>depth[t2]) swap(t1,t2);
        while(depth[t2]!=depth[t1]) {t2=par[t2];}
        while(t1!=t2) {t1=par[t1],t2=par[t2];}
        seq_push(i,a,t1,1);
        seq_push(i,b,t1,0);
        ans2.push_back(make_pair(a,b));
        for(int j=0;j<walk[i].size()-1;j++) {
            lotus[walk[i][j]][walk[i][j+1]].push_back(i);
            lotus[walk[i][j+1]][walk[i][j]].push_back(i);
        }
    }
    for(int i=0;i<m;i++) for(int j=0;j<walk[i].size()-1;j++) cnt[walk[i][j]][walk[i][j+1]]++,cnt[walk[i][j+1]][walk[i][j]]++;
    while(process());
    for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) ans+=min(cnt[i][j],2);//printf("%d %d %d\n",i,j,cnt[i][j]);
    printf("%d\n",ans);
    for(int i=0;i<m;i++) printf("%d %d\n",ans2[i].first,ans2[i].second);
}