← 返回题目列表

Codeforces · 786/E

E. 替代方案

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

ALT是一个位于名为“Encore”的星系中的行星。人类统治着这个星球,但由于某种原因,他们的星球上没有狗,所以那里的人们感到悲伤和沮丧。瑞克和莫蒂是普世慈善家,他们希望让 ALT 的人们幸福。

ALT 有 n 个城市,编号为 1 到 n 和 n - 1 条双向道路,编号为 1 到 n - 1。人们可以使用这些道路从任何城市前往任何其他城市。

ALT中有两类人:

1. 监护人。监护人住在路边的房子里,看守道路。
2. 公民。一个公民住在一个城市的房子里,在另一个城市的办公室工作。

ALT 上的每个人要么是监护人,要么是公民,并且每条道路旁只有一名监护人。

瑞克和莫蒂与 ALT 中的所有人进行了交谈,他们得到的结果如下:

- 有 m 位公民居住在 ALT。
- 公民 i 住在 xi 号城市,在 yi 号城市工作。
- 每个公民每天都会沿着从家到工作地点的最短路径穿过所有道路。
- 当且仅当他自己有一只小狗,或者他上班路上的所有监护人都有一只小狗(他在每条路上看到监护人的小狗并且会很高兴)时,一个公民才会幸福。
- 守护者总是快乐的。

你需要告诉瑞克和莫蒂他们需要多少只小狗才能让 ALT 中的所有人都满意,并提供分配这些小狗的最佳方式。

输入

输入的第一行包含两个整数 n 和 m (2 ≤ n ≤ 2 × 104, 1 ≤ m ≤ 104) — 分别是城市数量和公民数量。

接下来的 n - 1 行包含道路,第 i 行包含第 i 条边的端点、v 和 u (1 ≤ v, u ≤ n, v ≠ u)。

接下来的 m 行包含有关公民的信息。第 i 行包含两个整数 xi 和 yi (1 ≤ xi, yi ≤ n, xi ≠ yi)。

输出

在输入的第一行中打印一个整数 k,即它们需要的小狗总数 (1 ≤ k ≤ n)。

在第二行中打印一个整数 q,即要给予公民的小狗数量,后跟 q 个不同的整数 a1, a2, ..., aq,要给予小狗的公民索引 (0 ≤ q ≤ min(m, k), 1 ≤ ai ≤ m)。

在第三行中打印一个整数 e,即要给予监护人的小狗数量,后跟 e 个不同的整数 b1, b2, ..., be,要给予小狗的监护人道路索引 (0 ≤ e ≤ min(n - 1, k), 1 ≤ bi ≤ n - 1)。

q 和 e 之和应等于 k。

示例

输入 #1

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

输出 #1

3
1 5
2 3 1

输入 #2

4 7
3 4
1 4
2 1
4 2
4 2
2 4
1 4
2 1
3 1
4 2

输出 #2

3
1 6
2 2 3

注意

第一个示例测试用例中的 ALT 地图(道路上写的数字是其索引):

第二个示例测试用例中的 ALT 地图(道路上写的数字是其索引):