Problem Description

Given a tree with $N$ nodes, numbered from $1$ to $N$, there are sheep located at $K$ of these nodes. Your task is to distribute shepherds on the tree.

These shepherds are lazy and will only watch over the sheep closest to them. If there are multiple sheep at the same closest distance, the shepherd will watch over all of them.

A shepherd can be placed at the same node as a sheep, but in this case, the shepherd will only watch over that single sheep at that node.

Find a distribution of shepherds such that the total number of shepherds is minimized.

Input Format

The first line contains two integers $N$ and $K$, representing the number of nodes in the tree and the number of nodes with sheep, respectively.
The next $N-1$ lines each contain two integers $a_i$ and $b_i$, representing an edge in the tree.
The $N+1$-th line contains $K$ integers $o_i$, representing the node numbers where sheep are located.

Output Format

The first line contains an integer $X$, representing the minimum number of shepherds needed.
The second line contains $X$ integers, representing the nodes where each shepherd is placed.
If there are multiple solutions, output any one of them.

Sample Input and Output

Sample Input #1

4 2
1 2
2 3
3 4
1 4

Sample Output #1

2
1 3

Sample Input #2

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

Sample Output #2

3
1 4 9

Sample Input #3

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

Sample Output #3

3
5 14 18

Notes

Sample 3 Explanation

Data Constraints

This problem uses batched testing.

• Subtask 1 (8 pts): $1 \le N \le 5 \times 10^5$, every node $i$ is connected to node $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$.

For $100\%$ of the data, $1 \le K \le N$, $1 \le a_i, b_i \le N$, $1 \le o_i \le N$.

This problem uses a Special Judge. The checker was provided by @Lynkcat, and we thank him for his contribution.

Notes

Translated from the Croatian Olympiad in Informatics 2020 B Pastiri.

见题面 Input 部分

见题面 Output 部分