문제
Szeged에 온 Mr. Malnar은 평소처럼 현지 문화를 알아보고 모든 전통 음식, 요리 특산품, 지역 음료를 시도해야 하는 의무가 있습니다.
우리는 Szeged를 1부터 n까지의 번호가 매겨진 n개의 흥미로운 위치로 상상할 수 있으며, 각 위치 사이에는 n - 1개의 양방향 도로를 통해 연결되어 있습니다. 놀랍게도 Mr. Malnar은 모든 도로를 사용하여 각 흥미로운 위치 쌍 간의 경로가 있습니다. 놀라운 것은 Mr. Malnar이 각 도로를 걷는 데 정확히 1분이 걸린다는 것입니다. 흥미로운 위치에서 걷는 데 소요된 시간은 무시됩니다.
Mr. Malnar은 방문하고 싶은 m개의 레스토랑 목록이 있습니다. 이는 각각의 숫자가 i번째 레스토랑 근처의 흥미로운 위치를 나타내는 m개의 양의 정수로 구성되어 있습니다.
다른 문제는 Mr. Malnar이 레스토랑에서 식사한 후에 제과점에서 아이스크림을 먹어야 한다는 것입니다. 또 다른 문제는 동일한 제과점을 두 번 방문하지 않으려는 것입니다.
다행히 그는 m개의 위치에 대한 목록으로 기억하는 m개의 제과점을 알고 있습니다. 이 목록은 각각의 숫자가 i번째 제과점 근처의 흥미로운 위치를 나타내는 m개의 양의 정수로 구성되어 있습니다.
Mr. Malnar은 여행에서 피곤하고 도보로 이동할 필요가 없도록 원하지 않으므로 레스토랑과 제과점을 방문하는 데 얼마나 걸릴지와 도움 없이 이들 간을 이동할 순서를 계산해 달라고 요청합니다.
Mr. Malnar은 현재 흥미로운 위치 번호 1에 있으며 마지막에 이동해 다시 이곳으로 돌아와야 합니다.
입력
첫 번째 줄에는 n과 m이 주어지며, 흥미로운 위치의 수 및 레스토랑/제과점의 수입니다. (1 ≤ m ≤ n ≤ 3 · 10^5)
두 번째 줄에는 레스토랑의 목록인 m개의 정수 ai가 주어집니다. (1 ≤ ai ≤ n, i ≠ j일 때 ai ≠ aj)
세 번째 줄에는 제과점의 목록인 m개의 정수 bi가 주어집니다. (1 ≤ bi ≤ n, i ≠ j일 때 bi ≠ bj)
다음 n - 1개의 줄 각각에는 두 정수 xi와 yi가 주어지며 (1 ≤ xi, yi ≤ n), 이는 흥미로운 위치 xi와 yi 간에 도로가 있다는 것을 의미합니다.
출력
첫 번째 줄에는 Mr. Malnar이 모든 레스토랑과 제과점을 방문하여 마지막에 위치 1로 돌아가기까지 걸리는 시간 t를 출력합니다.
두 번째 줄에는 2m개의 정수 vi를 출력합니다. 레스토랑과 제과점의 방문 순서입니다.
홀수 위치의 숫자는 레스토랑을 나타내며 첫 m개의 양의 정수의 순열을 형성해야 합니다.
짝수 위치의 숫자는 제과점을 나타내며 첫 m개의 양의 정수의 순열을 형성해야 합니다.
주어진 순서로 각 위치를 방문하고 각 위치 사이를 최단 경로로 이동하여 정확히 t분이 걸립니다.
여러 최적의 순서가 있는 경우 아무거나 출력하면 됩니다.
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 20점 | |
| #2 | 20점 | |
| #3 | 점 | |
| #4 | 30점 | 추가 제약 조건 없음 |
예제 #1
3 1
2
3
1 2
1 3
4
1 1
Mr. Malnar은 레스토랑 2에 1분, 제과점 3에 2분 걷고, 마지막으로 1분 동안 위치 1로 돌아갑니다. Mr. Malnar은 총 4분 동안 걷습니다.
예제 #2
9 4
2 3 4 6
4 5 8 9
1 2
1 3
3 4
3 5
5 6
1 7
7 8
7 9
18
3 1 4 2 2 4 1 3
Mr. Malnar은 레스토랑 및 제과점을 다음과 같은 순서로 방문합니다: 레스토랑 4 (2분), 제과점 4 (0분), 레스토랑 6 (3분), 제과점 5 (1분), 레스토랑 3 (1분), 제과점 9 (3분), 레스토랑 2 (3분), 제과점 8 (3분). 마지막 아이스크림을 먹고 제 1 위치로 돌아갑니다 (2분). Mr. Malnar은 총 18분 동안 걷습니다.
예제 #3
10 5
3 5 6 7 8
1 2 4 9 10
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
24
4 4 5 5 3 3 2 2 1 1
Mr. Malnar은 레스토랑 및 제과점을 다음과 같은 순서로 방문합니다: 레스토랑 7 (6분), 제과점 9 (2분), 레스토랑 8 (1분), 제과점 10 (2분), 레스토랑 6 (4분), 제과점 4 (2분), 레스토랑 5 (1분), 제과점 2 (3분), 레스토랑 3 (1분), 제과점 1 (2분). 마지막 아이스크림을 먹으면 이미 위치 1에 있기 때문에 이동하지 않습니다. Mr. Malnar은 총 24분 동안 걷습니다.
로그인해야 코드를 작성할 수 있어요.