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 MN 2000
using namespace std;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
vector<int> v[MN+5];
pair<int,int> s[MN*MN+5];
int n,m,head[MN+5],cnt=0,same[MN*MN+5],ans[MN*MN+5],dfn[MN+5],dn,q[MN+5],M,Fa[MN+5],c[MN+5],Ans,dep[MN+5];
struct edge{int to,next;}e[MN*2+5];
inline void ins(int f,int t)
{
    e[++cnt]=(edge){t,head[f]};head[f]=cnt;
    e[++cnt]=(edge){f,head[t]};head[t]=cnt;
}
void Pre(int x)
{
    for(int i=head[x];i;i=e[i].next)
        if(e[i].to!=Fa[x]) dep[e[i].to]=dep[x]+1,Fa[e[i].to]=x,Pre(e[i].to);
    dfn[x]=++dn;q[dn]=x;
}
int lca(int x,int y)
{
    for(;x!=y;x=Fa[x]) if(dep[x]<dep[y]) swap(x,y);
    return x;
}
int main()
{
    n=read();M=m=read();
    for(int i=1;i<n;++i) ins(read(),read());
    Pre(1);
    for(int i=1;i<=m;++i)
    {
        s[i].first=read();s[i].second=read();
        ++c[s[i].first];++c[s[i].second];c[lca(s[i].first,s[i].second)]-=2;
        if(dfn[s[i].first]>dfn[s[i].second]) swap(s[i].first,s[i].second);
        v[s[i].first].push_back(i);
    }
    for(int i=1;i<=n;++i) c[Fa[q[i]]]+=c[q[i]],Ans+=min(c[q[i]],2);
    for(int i=1;i<n;++i)
    {
        int x=q[i],y;
        for(int j=head[x];j;j=e[j].next) if(dfn[e[j].to]>i) y=e[j].to;
        for(int j=v[x].size()>=2?2:0;j<v[x].size();++j)
        {
            int z=s[v[x][j]].second;
            if(z==y) continue;
            same[v[x][j]]=++m;
            if(dfn[y]<dfn[z]) s[m]=make_pair(y,z),v[y].push_back(m);
            else s[m]=make_pair(z,y),v[z].push_back(m),ans[v[x][j]]=1;
        }
        if(v[x].size()<2) continue;
        int a=s[v[x][0]].second,b=s[v[x][1]].second;
        if(a==b) {ans[v[x][0]]=1;continue;}
        if(dfn[a]<dfn[b]) s[++m]=make_pair(a,b),v[a].push_back(m),same[v[x][0]]=same[v[x][1]]=m,ans[v[x][0]]=1;
        else s[++m]=make_pair(b,a),v[b].push_back(m),same[v[x][0]]=same[v[x][1]]=m,ans[v[x][1]]=1;
    }
    printf("%d\n",Ans);
    for(int i=m;i;--i) if(same[i]) ans[i]^=ans[same[i]];
    for(int i=1;i<=M;++i) if(ans[i]) printf("%d %d\n",s[i].second,s[i].first); else printf("%d %d\n",s[i].first,s[i].second);
    return 0;
}