32336번 - 효율적으로 감찰하기 스페셜 저지

문제

조선에서 대대적인 비리 감찰을 진행할 예정이다. 문제는 신하들이 직접 전국을 돌아다녀야 하기에 굉장히 고되고 많은 시간이 든다는 것이다. 임금은 미래에서 온 여러분의 도움을 받아 효율적으로 감찰을 진행하고자 한다.

신하들은 지도와 각 신하가 방문해야 하는 장소를 정리한 표를 배정받았다. 지도에 적혀 있는 모든 장소는 0ドル$부터 $N-1$까지의 정수로 고유 번호가 하나씩 매겨져 있으며, 궁궐의 번호는 0ドル$번이다. 각 장소는 양방향 통행이 가능한 일정한 길이의 길로 모두 연결되어 있다. 신하들은 모두 궁궐(0ドル$번)에서 출발하여 지정된 모든 장소를 방문한 후, 궁궐로 돌아와 임금에게 보고드려야 한다. 이때, 한 장소에서 다른 장소로 이동할 때 주어진 길을 따라가야 하며, 이동하는 중간에 방향을 바꿀 수 없다고 하자.

신하들에게 제공된 지도는 편의를 위해 다음과 같이 설계되었다고 한다.

• 모든 장소는 총 $N-1$개의 길로 서로 연결되어 있다. 각 길은 양 끝의 두 장소만 연결한다.
• 한 장소에서 다른 장소로 이동할 수 있는 경로는 오직 하나만 존재한다.
• 길 하나를 따라 이동하는 데 걸리는 시간은 모두 단위 시간 1ドル$로 같다.

한 신하가 배정받은 지도와 표에 대한 정보가 주어질 때, 최소 시간으로 궁궐(0ドル$번)에 시작하여 지정된 정점을 모두 방문하고 궁궐로 돌아올 수 있게 하는 최적의 경로를 아무거나 하나 구해보자.

입력

첫 번째 줄에 장소의 수 $N$과 신하가 방문해야 하는 장소의 수 $M$이 공백으로 구분되어 주어진다. $(1 \leq N \leq 100,000円;$ 1ドル \leq M \leq N)$

두 번째 줄에 신하가 방문해야 하는 서로 다른 장소 $M$개의 번호 $p_1, p_2, \dots, p_M$이 공백으로 구분되어 주어진다. $(0 \leq p_i \leq N-1)$

이후 $N - 1$개의 줄에 걸쳐 $i+2$번째 줄에 $i$번째 길의 양 끝 장소의 번호 $u_i,ドル $v_i$가 공백으로 구분되어 주어진다. $(u_i \neq v_i;$ 0ドル \leq u_i, v_i \leq N-1)$

출력

첫 번째 줄에는 이동하는 데 걸린 최소 시간(단위 시간) $T$를 출력한다.

두 번째 줄에는 구한 최적의 경로 하나를 따라 이동하면서 방문한 각 장소 $T+1$개의 번호를 공백으로 구분하여 순서대로 출력한다.

제한

힌트