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