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