Від сутінків до світанку
Володимир має білу шкіру, дуже довгі зуби і йому 600 років, але це не проблема, адже Володимир — вампір. У Володимира ніколи не було проблем з тим, що він вампір. Насправді, він дуже успішний лікар, який завжди бере нічні зміни, тому має багато друзів серед своїх колег. У нього є вражаючий трюк, який він показує на вечірках: він може визначити групу крові на смак.
Володимир любить подорожувати, але, будучи вампіром, він має подолати три проблеми.
По-перше, він може подорожувати тільки поїздом, оскільки йому потрібно брати з собою свою труну. (З іншого боку, він завжди може подорожувати першим класом, адже вклав багато грошей у довгострокові акції.)
По-друге, він може подорожувати лише від сутінків до світанку, тобто з 18 години до 6 години. Протягом дня він має залишатися всередині вокзалу. По-третє, він має взяти з собою щось поїсти. Йому потрібен один літр крові на день, який він випиває опівдні (12:00) всередині своєї труни.
Ви повинні допомогти Володимиру знайти найкоротший маршрут між двома заданими містами, щоб він міг подорожувати з мінімальною кількістю крові. (Якщо він візьме занадто багато з собою, люди будуть ставити дивні запитання на кшталт "Що ви робите з усією цією кров'ю?")
Вхідні дані
Перший рядок вхідних даних міститиме одне число, яке вказує кількість тестових випадків. Кожна специфікація тестового випадку починається з одного числа, яке вказує, скільки специфікацій маршрутів слідує. Кожна специфікація маршруту складається з назв двох міст, часу відправлення з першого міста та загального часу подорожі. Часи вказані в годинах.
Зверніть увагу, що Володимир не може використовувати маршрути, які відправляються раніше 18:00 або прибувають пізніше 6:00. Буде не більше 100 міст і менше 1000 з'єднань. Жоден маршрут не займає менше однієї години і більше 24 годин. (Зверніть увагу, що Володимир може використовувати тільки маршрути з максимальною тривалістю подорожі 12 годин (від сутінків до світанку).) Усі назви міст коротші за 32 символи.
Останній рядок містить назви двох міст. Перше — місто відправлення Володимира, друге — місто призначення Володимира.
Вихідні дані
Для кожного тестового випадку ви повинні вивести номер тестового випадку, після якого
Володимиру потрібно # літр(ів) крові.
або
Немає маршруту, яким Володимир може скористатися.