From Dusk till Dawn (or Vladimir the Vampire)

Interview

Time limit1sMemory limit128 MB

Summary

Given nightly train routes between cities with departure and travel hours, find the route that minimizes the number of daytime waits, where a wait costs one litre of blood.

Level: Medium6 of 10
Topics: Graph, Shortest path, Sorting, Implementation
Solved: No attempts yet

Problem

Vladimir has white skin, very long teeth, and is 600 years old, but that is no problem at all, because Vladimir is a vampire.

Being a vampire has never troubled Vladimir. He is in fact a very successful doctor who always volunteers for the night shift, and he has made many friends among his colleagues. At dinner parties he loves to show off one impressive trick: he can name your blood group just by tasting it.

Vladimir loves to travel, but as a vampire he must work around three problems.

First, he can only travel by train, because he has to bring his coffin with him. (On the bright side, he can always afford first class thanks to some very long-term stock investments.)
Second, he can only travel from dusk till dawn, that is, from 18:00 (6 pm) to 6:00 (6 am). While the sun is up he must stay inside a train station.
Third, he has to bring food. He needs exactly one litre of blood per day, which he drinks at noon (12:00) inside his coffin.

Help Vladimir find a route between two given cities that lets him travel with the least possible amount of blood. (If he carries too much, people start asking awkward questions like "What do you do with all that blood?")

Concretely, Vladimir leaves the start city at dusk. During one night he may take several connecting trains, as long as each train departs no earlier than the moment he arrives at that station, and every train he uses departs no earlier than 18:00 and arrives no later than 6:00. If he has not reached the destination by dawn, he spends the day at whatever station he is in and drinks one litre of blood at the following noon, then travels on the next night. The amount of blood he needs equals the number of such daytime waits before he reaches the destination.

Input

The first line contains a single integer: the number of test cases.

Each test case begins with a single integer $R$ : the number of route descriptions that follow.

Each of the next $R$ lines describes one route in the format city1 city2 departure travel. The train runs from city1 to city2, leaving city1 at the whole hour departure and taking travel hours. All times are whole hours, and midnight may be written as 24. Vladimir cannot use a route that departs earlier than 18:00 or arrives later than 6:00, and therefore cannot use any route longer than 12 hours (dusk to dawn).

There are at most 100 cities and fewer than 1000 routes. Every route takes at least 1 hour and at most 24 hours. Every city name is shorter than 32 characters and contains no spaces.

The last line of each test case contains two city names: Vladimir's start city followed by his destination city.

Output

For each test case, first print the test-case number $k$ (starting from 1) as Test Case k.. On the next line, for the minimum required amount of blood $X$ , print

Vladimir needs X litre(s) of blood.

or, if no usable route exists, print

There is no route Vladimir can take.

Examples3

Example 1

Input

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

Expected output

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

Example 2

Input

1
1
Alpha Beta 18 5
Alpha Beta

Expected output

Test Case 1.
Vladimir needs 0 litre(s) of blood.

Example 3

Input

1
2
A B 18 2
B C 21 3
A C

Expected output

Test Case 1.
Vladimir needs 0 litre(s) of blood.