← 返回题目列表

Codeforces · 796/D

D. 警察局

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

Inzane终于发现Zane有很多闲钱,于是他们一起决定建立一个自己的国家。

统治一个国家并不是一件容易的事。小偷和恐怖分子随时准备破坏国家的和平。为了反击,赞恩和因赞恩制定了一项非常有效的法律:从每个城市出发,必须沿着道路行驶最多 d 公里才能到达警察局。

该国有 n 个城市,编号从 1 到 n,仅由 n - 1 条道路连接。所有道路均长 1 公里。最初可以使用这些道路从一个城市前往任何其他城市。该国还在一些城市设有 k 个警察局。特别是,城市的结构满足上述法律的要求。另请注意,一个城市可以有多个警察局。

然而,Zane 觉得拥有 n - 1 条道路是不必要的。该国正面临财政问题,因此希望通过关闭尽可能多的道路来最大限度地减少道路维护成本。

帮助赞恩找出在不违法的情况下可以关闭的最大道路数量。另外,帮助他确定这样的道路。

输入

第一行包含三个整数 n、k 和 d (2 ≤ n ≤ 3·105, 1 ≤ k ≤ 3·105, 0 ≤ d ≤ n - 1)——分别是城市数量、警察局数量和距离限制(以公里为单位)。

第二行包含 k 个整数 p1, p2, ..., pk (1 ≤ pi ≤ n) - 每个表示每个警察局所在的城市。

以下 n - 1 行中的第 i 行包含两个整数 ui 和 vi (1 ≤ ui, vi ≤ n, ui ≠ vi) - 由索引为 i 的道路直接连接的城市。

保证可以仅使用道路从一个城市前往任何其他城市。此外,从任何城市都可以到达 d 公里以内的警察局。

输出

在第一行中,打印一个整数s,表示可以关闭的最大道路数。

在第二行中,以任意顺序打印 s 个不同的整数,即此类道路的索引。

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

示例

输入 #1

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

输出 #1

1
5

输入 #2

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

输出 #2

2
4 5

注意

在第一个样本中,如果关闭 5 号公路,所有城市仍然可以到达 k = 4 公里范围内的警察局。

在第二个示例中,虽然这是唯一可以关闭的最大有效道路集,但您可以在第二行中打印 4 5 或 5 4。