描述

弗拉基米尔有着白皙的皮肤、长长的牙齿，已经 600 岁了，但这并不是问题，因为弗拉基米尔是一名吸血鬼。

作为一名吸血鬼，弗拉基米尔从未遇到过任何困扰。事实上，他是一位非常成功的医生，总是上夜班，因此在同事中结交了许多朋友。他在晚宴上有一个令人印象深刻的绝技：他能通过品尝来辨别血型。

弗拉基米尔热爱旅行，但作为一名吸血鬼，他必须克服三个问题。

首先，他只能乘坐火车旅行，因为他必须带着自己的棺材。（好的方面是，他总是能够乘坐头等舱，因为他在长期股票上进行了大量投资。） 其次，他只能在黄昏到黎明之间，也就是下午 6 点（18:00）到早上 6 点（06:00）之间旅行。在白天，他必须待在火车站内。 第三，他必须随身携带一些食物。他每天需要一升血，会在中午（12:00）在自己的棺材里饮用。 你应该帮助弗拉基米尔找到两个给定城市之间的最短路线，这样他就能携带最少数量的血出行。（如果他携带太多血，人们就会问一些奇怪的问题，比如“你拿这么多血做什么？”）

输入

输入的第一行将包含一个单独的数字，告诉你测试用例的数量。

每个测试用例的说明都以一个单独的数字开始，告诉你接下来有多少条路线说明。

每条路线说明由两个城市的名称、从第一个城市的出发时间以及总的旅行时间组成。时间以小时为单位。请注意，弗拉基米尔不能使用在 18:00 之前出发或在 06:00 之后到达的路线。

最多会有 100 个城市，并且连接数少于 1000 条。没有一条路线的耗时少于 1 小时或多于 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.

提示

出发时间可能会大于 24 点。

来源

乌尔姆本地赛 1999