← 返回题目列表

Codeforces · 748/F

F. 圣诞老人和足球锦标赛

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

国家 Treeland 由 n 个城市组成,并通过 n - 1 条双向道路连接,使得可以使用这些道路从任何其他城市出发到达每个城市。明年将举行足球锦标赛,所有参赛者都是圣诞老人。正好有来自 2k 个不同城市的 2k 支球队。

在第一阶段,所有队伍被分成 k 对。每对球队都会进行两场比赛:一场在第一队的家乡,另一场在另一队的家乡。因此,2k 个城市中的每一个都恰好举办一场足球比赛。不过,目前还没有决定如何将球队分成两组。

还需要选择几个城市来安置选手。组织者倾向于使用尽可能少的城市来安置队伍。

没有人愿意在锦标赛期间出差太多,所以如果一支球队在城市 u 和 v 比赛,它希望住在 u 和 v 之间最短路径上的城市之一(也许在 u 或 v 中)。还有另一个限制:一对队伍必须住在同一个城市。

综上所述,主办方希望将 2k 个团队分成两对,并在尽可能少的 m 个城市中定居,使得每对团队都居住在家乡之间的同一个城市。

输入

输入的第一行包含两个整数 n 和 k (2 ≤ n ≤ 2·105, 2 ≤ 2k ≤ n)——分别是 Treeland 中的城市数量和球队对的数量。

以下 n - 1 行描述了 Treeland 中的道路:每行包含两个整数 a 和 b (1 ≤ a, b ≤ n, a ≠ b),这意味着城市 a 和 b 之间有一条道路。保证任意两个城市之间都有路径。

最后一行包含 2k 个不同的整数 c1, c2, ..., c2k (1 ≤ ci ≤ n),其中 ci 是第 i 支球队的家乡。所有这些数字都是不同的。

输出

输出的第一行必须包含唯一的正整数 m,该整数应等于球队可以落户的最小可能城市数。

第二行应包含 m 个不同的数字 d1, d2, ..., dm (1 ≤ di ≤ n) 表示球队应落户的城市的索引。

接下来是 k 行,其中第 j 行应包含 3 个整数 uj、vj 和 xj,其中 uj 和 vj 是第 j 对球队的家乡,xj 是他们在比赛期间应该居住的城市。每个数字 c1、c2、...、c2k 应该在所有 uj 和 vj 中恰好出现一次。每个数字 xj 应该属于 {d1, d2, ..., dm}。

如果有多个可能的答案,请打印其中任何一个。

示例

输入 #1

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

输出 #1

1
2
5 4 2
6 2 2

注意

在第一个测试中,组织者可以将所有团队安置在2号城市中。将所有团队分成对的方式并不重要,因为无论如何都满足所有要求,因为城市2位于从{2,4,5,6}开始的每两个城市之间的最短路径上。