[AGC025E] Walking on a Tree

给定一棵 $n$ 个节点的树和 $m$ 条树上的路径, 要求为每一条路径定向. 第 $i$ 条树边 $(a_i, b_i)$ 的权值为满足下述条件的条数: - 被某条路径沿 $a_i\to b_i$ 方向经过. - 被某条路径沿 $b_i\to a_i$ 方向经过. 求最大权值和并给出 $m$ 条路经的定向方案, 多组方案合法输出任意一组即可. $n,m\leqslant 2000$

[problemUrl]: https://atcoder.jp/contests/agc025/tasks/agc025_e 高橋君は木上を散歩するのが大好きです。 高橋君が散歩をする木は $ 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 $ 回の散歩の楽しさの合計が最大になるように、各散歩の向きを決めたいです。 そこで、高橋君が得られる楽しさの合計の最大値と、実際に楽しさの合計が最大となる各散歩の向きの定め方の一例を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ 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 $ に向かって移動することを表している。

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

6
2 3
3 4
4 2

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

6
2 4
3 5
5 1

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

9
2 4
6 3
5 6
4 5

### 制約 - $ 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 $ - 入力で与えられるグラフは木である。 ### Sample Explanation 1 上のように散歩の向きを定めると、各散歩で $ 2 $ ずつ楽しさを得ることができ、合計の楽しさが $ 6 $ になります。