题目描述

高桥喜欢在树上散步。高桥散步的树有 $N$ 个编号为 $1$ 到 $N$ 的顶点。其中第 $N-1$ 条边连结了顶点 $a_i$ 和顶点 $b_i$。

高桥规划了 $M$ 次散步。第 $i$ 次散步的规则如下：

• 这次散步涉及到事先确定的两个顶点 $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$ 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