题目描述

译自 COI 2020 T2「Pastiri」

给定一棵 $N$ 点的树，点编号为 $1$ 到 $N$，现在在 $K$ 个点上有羊，你的任务是在树上分配一些牧羊人。

这些牧羊人很懒，只会看管离他最近的羊。当然如果有多个离他最近的羊，那么他会都看管。

当然，牧羊人可以和羊在同一个点上，但这样牧羊人只会看管这一个点上的那个羊。

求一种牧羊人的分配方案使得牧羊人总数最小。

输入格式

第一行两个整数 $N,K$ 代表树的点数和有羊的点数。
接下来 $N-1$ 行每行两个整数 $a_i,b_i$ 代表树的一条边。
第 $N+1$ 行 $K$ 个整数 $o_i$，代表有羊的点的编号。

输出格式

第一行一个整数 $X$ 代表牧羊人总数的最小值。
第二行 $X$ 个整数代表每个牧羊人分配到哪个点上。
如果有多种解，输出一种即可。

4 2
1 2
2 3
3 4
1 4

2
1 3

9 5
1 2
2 3
3 4
3 5
1 6
1 7
7 8
8 9
2 5 6 7 9

3
1 4 9

20 9
1 2
2 3
2 4
4 5
4 6
5 7
7 8
8 9
7 10
10 11
6 12
6 13
6 17
13 14
14 15
14 16
17 18
18 19
18 20
1 3 9 11 12 15 16 19 20

3
5 14 18

数据范围与提示

本题采用捆绑测试。

• Subtask 1（8 pts）：$1 \le N \le 5 \times 10^5$，任意一个点 $i$ 都与 $i+1$ 相连（$1 \le i \le N-1$）。
• Subtask 2（18 pts）：$1 \le K \le 15$，$1 \le N \le 5 \times 10^5$。
• Subtask 3（23 pts）：$1 \le N \le 2000$。
• Subtask 4（51 pts）：$1 \le N \le 5 \times 10^5$。

对于 $100\%$ 的数据，$1 \le K \le N$，$1 \le a_i,b_i \le N$，$1 \le o_i \le N$。