問題文

高橋君は木上を散歩するのが大好きです。 高橋君が散歩をする木は $N$ 頂点からなり、各頂点には $1$ から $N$ の番号が割り振られています。 また、$N-1$ 本の辺のうち、$i$ 本目の辺は頂点 $a_i$ と頂点 $b_i$ を結んでいます。

高橋君は $M$ 回の散歩の予定を組みました。$i$ 回目の散歩は以下のようにして行う予定です。

• $2$ つの頂点 $u_i,v_i$ が決まっている。
• 高橋君は頂点 $u_i$ から頂点 $v_i$、または、頂点 $v_i$ から頂点 $u_i$ に向かって、同じ辺は一度しか通らないように移動する。

また、$i$ 回目の散歩で得られる 楽しさ は以下のように定義されています。

• $i$ 回目の散歩で通った辺であって、以下のいずれかの条件を満たすものの個数
  • 今回の散歩で初めて通った辺
  • 今まで通ったことがあっても、今回とは逆向きでしか通っていなかった辺

高橋君は $M$ 回の散歩の楽しさの合計が最大になるように、各散歩の向きを決めたいです。 そこで、高橋君が得られる楽しさの合計の最大値と、実際に楽しさの合計が最大となる各散歩の向きの定め方の一例を求めてください。

制約

• $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$
• 入力で与えられるグラフは木である。

入力

入力は以下の形式で標準入力から与えられる。

$N$ $M$ $a_1$ $b_1$ : $a_{N-1}$ $b_{N-1}$ $u_1$ $v_1$ : $u_M$ $v_M$

出力

高橋君が得られる楽しさの合計の最大値 $T$ と、実際に楽しさの合計が最大となる各散歩の向きの定め方の一例を、以下の形式に従って出力せよ。

$T$ $u'_1$ $v'_1$ : $u'_M$ $v'_M$

ただし、($u'_i$,$v'_i$) は ($u_i$,$v_i$) または ($v_i$,$u_i$) であり、$i$ 回目の散歩で $u'_i$ から $v'_i$ に向かって移動することを表している。

入力例 1

4 3
2 1
3 1
4 1
2 3
3 4
4 2

出力例 1

6
2 3
3 4
4 2

上のように散歩の向きを定めると、各散歩で $2$ ずつ楽しさを得ることができ、合計の楽しさが $6$ になります。

入力例 2

5 3
1 2
1 3
3 4
3 5
2 4
3 5
1 5

出力例 2

6
2 4
3 5
5 1

入力例 3

6 4
1 2
2 3
1 4
4 5
4 6
2 4
3 6
5 6
4 5

出力例 3

9
2 4
6 3
5 6
4 5