Maria-səyahətçi#6315
Марія Зеленчук дуже любила подорожувати. Вона могла подорожувати тільки з батьком, професором. Якось професора Зеленчука запросили на конгрес на дуже віддалену планету, на іншому кінці галактики. Оскільки "Пегас" був на ремонті, професор вирішив скористатися громадським транспортом — телепортаційними воротами. Подорож через такі ворота займає одну одиницю (хвилину) галактичного часу, але ворота доступні лише у певні проміжки часу, і для подорожі між планетами необхідно, щоб ворота на обох планетах були доступні протягом усього процесу перенесення. Крім того, з кожної планети через ворота можна потрапити лише на обмежену кількість інших планет, і не завжди з'єднання є двосторонніми.
Ознайомившись з розкладом роботи воріт, професор (нагадаємо, космозоолог) був у розпачі. Довелося робити багато пересадок, і знайти маршрут виявилось складно. Він пообіцяв Марії взяти її з собою, якщо вона знайде найлегший шлях, щоб потрапити на конгрес. Зверніть увагу, що час перебування на кожній планеті незначний і може вважатися нульовим.
У першому рядку задано одне натуральне число N, (2 ≤ N ≤ 10000) — кількість планет з воротами.
Далі наведено 3 рядки інформації про кожну планету; кожні 3 послідовні рядки описують одну планету. Перший рядок містить назву планети (до 10 символів, маленькими латинськими літерами). Усі назви відрізняються. Другий рядок містить список планет, які можна досягнути через ворота: назви через пробіл. Третій рядок містить інформацію про доступність воріт. У кожному рядку перше число M_i (1 ≤ M_i ≤ 15) — кількість проміжків часу, коли ворота відкриті, потім 2M_i невід'ємних цілих чисел (кожне не перевищує 10^9) — початок і кінець роботи воріт для кожного проміжку. Проміжки не перетинаються та не обов'язково впорядковані.
В останніх двох рядках містяться назви планет, через які треба організувати подорож: з тієї, де Марія, вказана у передостанньому рядку, до тієї, де буде конгрес, вказаної у останньому.
Відомо, що сума довжин усіх списків планет, яких можна досягнути через ворота, не перевищує 100000.
У єдиному рядку виведіть одне ціле число — мінімальний час, за який Марія з батьком можуть дістатися конгресу, якщо почнуть шлях о 0. Якщо це неможливо, виведіть -1.
Nümunə 1