황혼에서 새벽까지 (혹은 뱀파이어 블라디미르)

블라디미르는 피부가 창백하고 이빨이 아주 길며 나이가 600살이지만, 그것은 전혀 문제가 되지 않습니다. 블라디미르는 뱀파이어이기 때문입니다.

블라디미르는 뱀파이어라는 사실로 곤란을 겪은 적이 한 번도 없습니다. 오히려 그는 늘 야간 근무를 자원하는 매우 성공한 의사이며, 동료들 사이에 친구도 많습니다. 저녁 모임에서 그가 즐겨 선보이는 인상적인 재주가 하나 있는데, 바로 피를 맛보기만 하고 혈액형을 알아맞히는 것입니다.

블라디미르는 여행을 좋아하지만, 뱀파이어이기 때문에 세 가지 문제를 해결해야 합니다.

• 첫째, 관을 가지고 다녀야 하므로 오직 기차로만 이동할 수 있습니다. (대신 장기 주식 투자로 큰돈을 벌어 두어서 언제나 일등석을 탈 수 있습니다.)
• 둘째, 해 질 녘부터 동틀 녘까지, 즉 18시(오후 6시)부터 6시(오전 6시)까지만 이동할 수 있습니다. 낮 동안에는 기차역 안에 머물러야 합니다.
• 셋째, 먹을 것을 챙겨야 합니다. 하루에 정확히 1리터의 피가 필요하며, 이 피는 정오(12시)에 관 속에서 마십니다.

블라디미르가 가능한 한 적은 양의 피만 가지고 두 도시 사이를 이동할 수 있도록 그를 위한 경로를 찾아 주세요. (피를 너무 많이 들고 다니면 사람들이 "그 피를 다 어디에 쓰나요?" 같은 곤란한 질문을 하기 때문입니다.)

구체적으로, 블라디미르는 해 질 녘에 출발 도시를 떠납니다. 하룻밤 동안 여러 기차를 갈아탈 수 있는데, 갈아탈 때마다 그 역에 도착한 시각 이후(같은 시각 포함)에 출발하는 기차만 탈 수 있고, 이용하는 모든 기차는 18시보다 이르게 출발하거나 6시보다 늦게 도착해서는 안 됩니다. 동틀 녘까지 목적지에 도착하지 못하면 그 시각에 머물러 있는 역에서 낮을 보내고, 이어지는 정오에 피 1리터를 마신 뒤 다음 밤에 다시 이동합니다. 그가 필요로 하는 피의 양은 목적지에 도착하기 전까지 이렇게 낮을 보내며 기다린 횟수와 같습니다.

첫 줄에는 테스트 케이스의 수를 나타내는 정수 하나가 주어집니다.

각 테스트 케이스는 이어지는 노선 설명의 개수를 나타내는 정수 $R$ 하나로 시작합니다.

그다음 $R$개의 줄에는 각각 하나의 노선이 도시1 도시2 출발시각 이동시간 형식으로 주어집니다. 이 기차는 도시1에서 도시2로 가며, 도시1을 정각 출발시각에 떠나 이동시간시간 동안 달립니다. 모든 시각과 시간은 정수 시간 단위이며, 자정은 24로 주어질 수 있습니다. 블라디미르는 18시보다 이르게 출발하거나 6시보다 늦게 도착하는 노선을 이용할 수 없으며, 따라서 12시간(해 질 녘부터 동틀 녘까지)을 넘는 노선도 이용할 수 없습니다.

도시는 최대 100개, 노선은 1000개 미만입니다. 모든 노선의 이동 시간은 1시간 이상 24시간 이하입니다. 모든 도시 이름은 32자 미만이며 공백을 포함하지 않습니다.

각 테스트 케이스의 마지막 줄에는 두 도시 이름이 주어집니다. 첫 번째는 블라디미르의 출발 도시, 두 번째는 목적지 도시입니다.

각 테스트 케이스마다 먼저 Test Case k. 형식으로 테스트 케이스 번호 $k$(1부터 시작)를 출력합니다. 그다음 줄에, 최소로 필요한 피의 양 $X$에 대해

Vladimir needs X litre(s) of blood.

를 출력하고, 이용할 수 있는 경로가 없으면

There is no route Vladimir can take.

를 출력합니다.