16216번 - 우산

그대는 내 머리 위의 우산, 어깨 위에 차가운 비 내리는 밤, 내 곁에 그대가 없는 반쪽의 세상, 그댄 나 없이는 안 돼요.

- <우산>, 윤하

윤하는 트리 구조를 한 도시에 살고 있다. 도시에는 비가 오고 있다. 도시의 정점은 N개로, 1번부터 N번까지 번호가 붙어 있다.

윤하는 방문하고 싶은 K개의 서로 다른 정점들을 골랐다. 윤하는 지금 1번 정점에 있다. 각 간선이 잇는 두 정점 사이를 이동하는 데에는 1초의 시간이 걸린다. 윤하는 K개의 정점들 중 몇 개를 지금 방문하려 한다. K개의 정점들 중 1개, 2개, …, K개를 방문하는 데 필요한 최소의 시간을 계산해 주자.

하나의 정점을 여러 번 방문할 때에는 첫 번째 방문만 셈한다는 것, 그리고 정점들을 방문한 뒤에 윤하가 1번 정점에 다시 돌아올 필요가 없다는 것에 유의하자.

첫 줄에 정점의 개수 N과 윤하가 방문하고 싶은 정점의 개수 K가 주어진다. (1 ≤ N ≤ 300,000, 1 ≤ K ≤ 5,000, K < N)

둘째 줄부터 N-1개의 줄에는 윤하가 사는 도시의 간선들이 잇는 정점들의 번호를 나타내는 두 정수 a_i와 b_i가 주어진다. (1 ≤ a_i, b_i ≤ N, a_i ≠ b_i)

마지막 줄에는 윤하가 방문하고 싶은 정점들의 번호를 나타내는 서로 다른 K개의 정수 c₁, ..., c_K가 공백을 사이에 두고 주어진다. (c_i ≠ 1)

윤하가 방문하고 싶은 정점들 중 1개, 2개, …, K개를 방문하기 위해 필요한 최소 시간을 공백을 사이에 두고 순서대로 출력하라.