Description

Given a tree with $N$ nodes labeled from $1$ to $N$, there are sheep on $K$ nodes. Your task is to place some shepherds on the tree.

These shepherds are lazy: each shepherd will only watch the sheep that are closest to them. Of course, if there are multiple closest sheep, the shepherd will watch all of them.

A shepherd may be placed on the same node as a sheep, but in that case, the shepherd will only watch the sheep on that node.

Find a placement of shepherds that minimizes the total number of shepherds.

Input Format

The first line contains two integers $N, K$, representing the number of nodes in the tree and the number of nodes with sheep.
The next $N - 1$ lines each contain two integers $a_i, b_i$, representing an edge of the tree.
The $(N + 1)$-th line contains $K$ integers $o_i$, representing the labels of the nodes that have sheep.

Output Format

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

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

Hint

Explanation for Sample 3

Constraints

This problem uses bundled testdata.

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

Notes

Translated from Croatian Olympiad in Informatics 2020 B Pastiri.

Translated by ChatGPT 5