题目描述

高桥君非常喜欢在树上散步。高桥君散步的树由 $N$ 个顶点组成，每个顶点被编号为 $1$ 到 $N$。此外，$N-1$ 条边中的第 $i$ 条边连接顶点 $a_i$ 和顶点 $b_i$。

高桥君计划进行 $M$ 次散步。第 $i$ 次散步将按以下方式进行：

• 确定两个顶点 $u_i$ 和 $v_i$。
• 高桥君将从顶点 $u_i$ 移动到顶点 $v_i$，或者从顶点 $v_i$ 移动到顶点 $u_i$，且同一条边不会被重复经过。

此外，第 $i$ 次散步的乐趣定义如下：

• 在第 $i$ 次散步中经过的边中，满足以下任一条件的边的数量：
  • 本次散步中首次经过的边；
  • 之前曾经经过但仅以相反方向经过的边。

高桥君希望通过为每次散步选择方向，使得 $M$ 次散步的总乐趣最大化。因此，请计算高桥君能够获得的最大总乐趣，并给出一个实际使总乐趣最大的散步方向设定示例。

输入格式

输入通过标准输入给出，格式如下：

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

输出格式

输出高桥君能够获得的最大总乐趣 $T$，以及一个实际使总乐趣最大的散步方向设定示例，格式如下：

$T$
$u'_1$ $v'_1$
$\vdots$
$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

输出

6
2 3
3 4
4 2

样例 2

输入

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

输出

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

输出

9
2 4
6 3
5 6
4 5

说明/提示

约束条件

• $1 \leq N, M \leq 2000$
• $1 \leq a_i, b_i \leq N$
• $1 \leq u_i, v_i \leq N$
• $a_i \neq b_i$
• $u_i \neq v_i$
• 输入给出的图是一棵树。

样例解释 #1

按照上述方式设定散步方向后，每次散步可以获得 $2$ 点乐趣，总乐趣为 $6$。

翻译由 DeepSeek V3 完成