From Dusk Till Dawn

블라디미르는 새하얀 피부와 날카로운 이를 가지고 있다. 나이는 600살이나 되지만, 뱀파이어인 블라디미르에게 나이는 별 의미가 없다. 블라디미르는 뱀파이어로 살아가는 데 있어서 별 다른 불편함을 느끼지 못한다. 그는 항상 야간 근무를 맡는 의사로 일하고 있는데, 훌륭하게 의사 생활을 하고 있으며, 야간 근무를 도맡아 하다 보니 동료들하고도 매우 사이 좋게 지내고 있다. 그는 파티장에서 맛을 보는 것만으로도 혈액형을 알마맞히는 쇼를 보여주곤 한다. 블라디미르는 여행을 하고 싶은데, 뱀파이어이다 보니 세 가지 문제를 극복해야만 한다.
{{| 1. 항상 관을 가지고 다녀야 하기 때문에 기차 여행 밖에는 할 수가 없다. 다행히도 워낙 오랫동안 돈을 모았기 때문에 재력이 상당하므로 항상 1등칸을 타고 다닐 수 있다.

1. 황혼에서 새벽까지만, 즉 오후 여섯 시부터 오전 여섯 시까지만 여행할 수 있다. 낮에는 기차역을 벗어날 수 없다.
   
2. 뭔가 먹을 것을 가지고 다녀야 한다. 하루에 피를 1리터씩 먹어야 하며, 그의 관 안에서 정오(낮 12시)에 피를 마신다. |}}
   

두 도시가 주어졌을 때 최단 경로를 찾는 프로그램을 만들어서 블라디미르가 최소한의 피만 챙겨서 여행할 수 있도록 도와주자. 피를 너무 많이 가지고 다니면 사람들이 "그 피 가지고 뭘 하실 건가요?" 같은 질문을 하면서 의심할 수도 있기 때문이다.

첫번째 줄에는 테스트 케이스의 개수를 나타내는 정수 한 개가 입력된다. 각 테스트 케이스의 첫번째 줄에는 그 밑에서 몇 개의 열차 노선을 설명할 것인지를 나타내는 정수 한 개가 입력된다. 각 노선을 설명하는 부분에는 두 도시의 이름, 첫번째 도시에서의 출발 시각, 그리고 총 여행 시간이 입력된다. 출발 시각은 반드시 정각이며, 여행 시간은 정확하게 정수 단위의 시간으로 표현된다. 블라디미르는 18:00 이전에 출발할 수 없으며 6:00 이후에 도착해서도 안 된다는 점을 꼭 기억해 두자.
도시의 개수는 최대 100개며, 열차 노선(서로 다른 출발 시각 포함)은 1,000개를 넘지 않는다. 여행 시간이 한 시간 미만이거나 24시간 이상인 노선은 없지만, 블라디미르가 탈 수 있는 노선은 주어진 시간 내에서만 12시간 이내로 여행하는 것으로 제한된다.
모든 도시 이름은 최대 32글자로 주어진다. 마지막 줄에는 두 개의 도시 이름이 입력되는데, 첫번째 도시 이름은 출발지 이름, 두번째 도시 이름은 도착지 이름이다.

각 테스트 케이스에 대해 일단 테스트 케이스 번호를 출력한 다음, 그 다음 줄에 "Vladimir needs # litre(s) of blood." 또는 "There is no route Vladimir can take."를 출력한다 (출력 예 참조).

{{| 2
3
Ulm Muenchen 17 2
Ulm Muenchen 19 12
Ulm Muenchen 5 2
Ulm Muenchen
10
Lugoj Sibiu 12 6
Lugoj Sibiu 18 6
Lugoj Sibiu 24 5
Lugoj Medias 22 8
Lugoj Medias 18 8
Lugoj Reghin 17 4
Sibiu Reghin 19 9
Sibiu Medias 20 3
Reghin Medias 20 4
Reghin Bacau 24 6
Lugoj Bacau |}}

{{| Test Case 1.
There is no route Vladimir can take.
Test Case 2.
Vladimir needs 2 litre(s) of blood. |}}

----
문제분류 경시대회준비반