← 返回题目列表

AtCoder · agc025_e

E. 在树上行走

中文机器翻译题面 查看原题

分数: 1500 点

问题陈述

高桥喜欢在树上行走。 高桥走过的树有 N 顶点编号 1 通过 N。 的 网格的 i- 第 N-1 边连接顶点 a_i 和顶点 b_i.

高桥已安排 M 行走。的 i第步行完成如下:

  • 行走涉及两个顶点 u_i 和 v_i 已预先修复。
  • 高桥将步行从 u_i to v_i 或来自 v_i to u_i 沿着最短路径。

的 幸福 获得自 i-th walk 定义如下:

  • 获得的幸福感是在该过程中遍历的边的数量 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-th 步从顶点开始 u^'_i to 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