Марія-мандрівниця#6315
Марія Зеленчук дуже любила подорожувати. Вона могла подорожувати лише тоді, коли її брав із собою батько, професор. Одного разу професора Зеленчука запросили на конгрес на дуже далеку планету, розташовану на іншому кінці галактики. Оскільки "Пегас" був у ремонті, професор вирішив скористатися громадським транспортом — телепортаційними воротами. Подорож через такі ворота займає одну одиницю (хвилину) галактичного часу, але ворота доступні лише в певні проміжки часу. Для подорожі між планетами необхідно, щоб ворота на обох планетах були доступні протягом усього процесу перенесення. Крім того, з кожної планети через ворота можна потрапити лише на обмежений набір планет, і не завжди планети доступні в обидва боки.
Ознайомившись з розкладом роботи воріт, професор (нагадаємо, космозоолог) схопився за голову. Подорож вимагатиме багатьох пересадок, і скласти маршрут виявилося складно. Він пообіцяв взяти Марію з собою, якщо їй вдасться знайти найкоротший за часом маршрут, що дозволяє потрапити на конгрес. Зазначимо, що час перебування на кожній з планет нехтовно малий, і його можна вважати нульовим.
У першому рядку одне натуральне число , ( ≤ ≤ ), — кількість планет з воротами.
Далі йде рядки інформації про планети, кожні послідовні рядки описують одну планету. Перший рядок опису містить назву планети (довжиною до символів, назва складається з малих латинських літер). Усі назви планет різні. Другий рядок опису планети містить список планет, доступних з неї через ворота: відокремлені один від одного пробілами назви планет, обладнаних воротами. Третій рядок опису планети описує час доступності. У кожному рядку перше число M_i ( ≤ M_i ≤ ) означає кількість діапазонів часу, коли ворота доступні, потім слідує 2M_i невід'ємних цілих чисел (кожне не перевищує 10^9), відокремлених один від одного пробілами. Кожна пара чисел означає час початку і кінця роботи воріт (діапазони часу не перетинаються, але не зобов'язані бути упорядкованими).
В останніх двох рядках файлу містяться назви планет, між якими потрібно організувати подорож від планети, вказаної в передостанньому рядку файлу, де знаходиться Марія, до планети, вказаної в останньому рядку файлу, де проходить конгрес.
Відомо, що сума довжин усіх списків планет, доступних через ворота, не перевищує .
В єдиному рядку одне ціле число — мінімальний час, за який Марія з батьком можуть потрапити на конгрес, якщо спробують почати подорож у момент часу . При відсутності можливості потрапити на конгрес вивести .
Приклад 1