Einbahnstrasse

Einbahnstraße(독일어로 '일방통행로')는 차량이 한 방향으로만 이동할 수 있는 도로입니다. 일방통행로를 두는 이유 중 하나는 혼잡한 지역에서 교통 흐름을 더 원활하게 하기 위함입니다. 이는 도시 중심가, 특히 카이로나 다마스쿠스 같은 오래된 도시에서 유용합니다. 잘 짜인 계획 덕분에 어느 지점에서 출발하더라도 임의의 장소에 도달할 수 있습니다. 그럼에도 운전자는 일방통행로 때문에 이동이 길어지지 않도록 경로를 신중하게 계획해야 합니다. 숙련된 운전자는 두 장소 사이에 여러 경로가 있음을 압니다. 게다가 같은 두 장소를 잇는 도로가 여러 개일 수도 있습니다. 두 장소 사이의 최단 경로를 아는 것은 필수이며, 조작이 어려운 차량(쓰레기차, 견인차 등)을 운전할 때는 더욱 그렇습니다.

당신은 견인 회사에 막 취직했습니다. 회사는 차고에 여러 대의 견인차를 두고 있습니다. 견인차는 고장 난 차의 앞바퀴나 뒷바퀴를 들어 올려 곧장 회사 차고로 끌고 옵니다. 당신은 도시 곳곳에서 견인이 필요한 고장 차량에 대한 전화를 받으며, 차량은 전화를 받은 순서대로 견인해야 합니다. 당신의 임무는 모든 고장 차량을 차고로 모으는 최단 경로를 견인차 기사에게 안내하는 것입니다. 하루가 끝나면 트럭들이 이동한 총 거리를 경영진에게 보고해야 합니다.

프로그램은 하나 이상의 테스트 케이스로 검증됩니다. 각 테스트 케이스의 첫 줄에는 하나 이상의 공백으로 구분된 세 수 $N$, $C$, $R$이 주어집니다. 도시에는 회사 차고를 포함하여 서로 다른 이름을 가진 $N$개의 장소가 있습니다. $C$는 고장 난 차량의 수, $R$은 도시의 도로 수입니다. 제약은 $0 < N < 100$, $0 \le C < 1000$, $R < 10000$입니다. 둘째 줄은 $C + 1$개의 단어로 이루어지며, 첫 단어는 회사 차고의 위치이고 나머지는 고장 난 차량들의 위치입니다. 장소 이름은 10글자 이하의 단어이며 대소문자를 구분합니다. 둘째 줄 다음에는 도로를 설명하는 줄이 정확히 $R$개 이어집니다. 각 도로는 다음 세 형식 중 하나로 표현됩니다.

A --v-> B
A <-v-- B
A <-v-> B

$A$와 $B$는 서로 다른 두 장소의 이름이고, $v$는 도로의 길이를 나타내는 양의 정수(1000 이하)입니다. 첫 번째 형식은 $A$에서 $B$로 가는 일방통행로, 두 번째 형식은 $B$에서 $A$로 가는 일방통행로, 세 번째 형식은 두 장소를 잇는 양방향 도로를 뜻합니다. $A$, 화살표, $B$는 하나 이상의 공백으로 구분됩니다. 입력의 끝은 $N$, $C$, $R$이 모두 0인 줄로 표시됩니다.

각 테스트 케이스마다 트럭들이 이동한 총 거리를 다음 형식으로 출력합니다.

k. V

여기서 $k$는 테스트 케이스 번호(1부터 시작), 점 다음에는 공백이 하나 오고, $V$는 결과 값입니다.

각 고장 차량은 개별적으로 견인됩니다. 즉, 견인차는 차고에서 출발해 고장 차량의 위치까지 갔다가 다시 차고로 돌아옵니다. 따라서 총 거리는 모든 고장 차량에 대해 (차고에서 차량 위치까지의 최단 거리) + (차량 위치에서 차고까지의 최단 거리)를 합한 값입니다. 같은 두 장소를 잇는 도로가 여러 개이면 가장 짧은 것을 사용합니다.