운송 경로

한 운송 회사가 고객에게 배송 비용을 빠르게 견적해 주는 프로그램을 필요로 한다. 배송 비용은 화물의 크기와 필요한 운송 구간(leg)의 수에 따라 결정된다. 하나의 운송 구간은 서로 다른 두 창고를 연결한다. 모든 창고 쌍이 직접 연결되어 있는 것은 아니므로, 한 창고에서 다른 창고로 화물을 보내려면 여러 개의 구간을 거쳐야 할 수도 있다.

하나의 데이터 집합은 1개에서 30개까지의 창고를 나타낸다. 각 창고는 대문자 두 글자로 이루어진 코드로 식별된다. 운송 구간은 서로 다른 임의의 두 창고 사이에 존재할 수 있으며, 모든 구간은 양방향이다.

배송 비용은 (화물의 크기) × (필요한 운송 구간의 수) × $100 이다.

창고 목록과 존재하는 운송 구간이 주어지고, 화물 크기·출발 창고·도착 창고로 이루어진 요청이 주어졌을 때, 가장 적은 구간을 거치는 가장 저렴한 배송 비용을 출력한다. 출발 창고에서 도착 창고로 가는 경로가 존재하지 않으면 배송이 불가능함을 알린다.

첫 번째 줄에는 데이터 집합의 개수를 나타내는 정수 $T$ ($1 \le T \le 10$)가 주어진다. 각 데이터 집합은 서로 다른 배송 구성을 나타낸다.

각 데이터 집합의 첫 줄에는 세 정수 $M$, $N$, $P$가 주어진다.

• $M$ ($1 \le M \le 30$): 창고의 수
• $N$ ($0 \le N \le M(M-1)/2$): 운송 구간의 수
• $P$ ($0 \le P \le 10$): 배송 요청의 수

다음 줄에는 $M$개의 두 글자 창고 코드(대문자만 사용)가 공백 하나로 구분되어 주어진다.

이어지는 $N$개의 줄에는 각각 서로 다른 두 창고 코드 XX YY가 주어지며, 이는 XX와 YY 사이에 직접 연결된 양방향 운송 구간이 있음을 뜻한다.

마지막 $P$개의 줄에는 배송 요청이 한 줄에 하나씩 주어진다. 각 요청은 화물 크기 정수 $S$ ($1 \le S \le 20$)와 서로 다른 두 창고 코드 AA BB(각각 출발 창고와 도착 창고)로 이루어진다.

입력은 항상 유효하고 일관적이다. 각 운송 구간은 한 데이터 집합 안에서 최대 한 번만 등장하며, 모든 코드는 해당 데이터 집합에 속한 창고를 가리킨다.

각 데이터 집합에 대해 순서대로 다음을 출력한다.

• DATA SET k를 출력한다. 여기서 k는 1부터 시작하는 데이터 집합 번호이다.
• 빈 줄 하나를 출력한다.
• $P$개의 결과 줄을 출력한다. 각 요청에 대해 가장 저렴한 비용을 $A 형태(달러 기호 바로 뒤에 정수 금액 $A$를 붙인 형태, 예: $500)로 출력하거나, 출발 창고에서 도착 창고로 가는 경로가 없으면 NO SHIPMENT POSSIBLE을 출력한다.

연속한 두 데이터 집합 사이는 빈 줄 하나로 구분한다.