시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 512 MB53171226.087%

문제

"I never felt so full that I couldn’t eat one more lamb." – Mr. Malnar

A flock of K sheep lives in a tree, a simple connected graph without a cycle. The tree contains N nodes denoted with integers from 1 to N. Each node of a tree is a home to at most one sheep. A wise shepherd realized that, sooner or later, wolves will learn how to climb trees.

In order to protect the sheep, we need to place shepherds into some nodes such that each sheep is protected by at least one shepherd. It is known that each shepherd protects all sheep that are closest to him, and only them. The distance between some sheep and some shepherd is equal to the number of nodes on a unique path between the node containing the sheep and the node containing the shepherd (inclusive). Additionally, the shepherd can share a node with a sheep. Of course, in that case he protects only that sheep.

Determine the minimal number of shepherds that need to placed in the nodes of a tree such that each sheep is protected by at least one shepherd. Additionally, determine one such arrangement of shepherds.

입력

The first line contains integers N and K (1 ≤ K ≤ N) from the task description.

Each of the next N − 1 lines contains two integers ai and bi (1 ≤ ai, bi ≤ N) which indicate that there is an undirected edge between nodes ai and bi.

The next line contains K different integers oi (1 ≤ oi ≤ N) that represent nodes which containing a sheep.

출력

In the first line you should output a number X which represents the minimal number of shepherds from the task description.

In the second line you should output X space-separated integers which represent the nodes containing shepherds.

If there are multiple correct solutions, you may output any of them.

서브태스크

번호배점제한
18

1 ≤ N ≤ 500 000, every node x = 1, . . . , n − 1 is connected with node x + 1

218

1 ≤ K ≤ 15, 1 ≤ N ≤ 500 000

323

1 ≤ N ≤ 2 000

451

1 ≤ N ≤ 500 000

예제 입력 1

4 2
1 2
2 3
3 4
1 4

예제 출력 1

2
1 3

예제 입력 2

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

예제 출력 2

3
1 4 9

예제 입력 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

예제 출력 3

3
5 14 18

채점 및 기타 정보

  • 예제는 채점하지 않는다.