AT_agc025_e [AGC025E] Walking on a Tree

[problemUrl]: https://atcoder.jp/contests/agc025/tasks/agc025_e 高桥君非常喜欢在树上散步。高桥君散步的树由 $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 \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 完成