分数: 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