Alice the Traveler
Alice Selezneva, from the famous works of Kir Bulychev, loved to travel. She could only travel if her father, the professor, took her along. One day, Professor Seleznev received an invitation to a congress on a distant planet located at the far end of the galaxy. Since their spaceship, "Pegasus," was under repair, the professor decided to use public transportation via teleportation gates. Traveling through these gates takes one unit (minute) of galactic time, but the gates are only operational during specific time intervals. To travel between planets, the gates on both planets must be available for the entire duration of the transfer. Additionally, each planet has a limited set of other planets it can reach through the gates, and not all connections are bidirectional.
Upon examining the gate schedule, the professor, who is a space zoologist, was overwhelmed. The journey required numerous transfers, and finding a route was challenging. He promised Alice that she could accompany him if she managed to find the shortest route to the congress. Note that the time spent on each planet is negligible and can be considered zero.
Input
The first line contains a single natural number N (2 ≤ N ≤ 10000), representing the number of planets with gates.
Following this are 3 lines of information for each planet, with every 3 consecutive lines describing one planet. The first line of each description contains the planet's name (up to 10 characters long, consisting of lowercase Latin letters). All planet names are unique. The second line lists the planets accessible from it via the gates: planet names equipped with gates, separated by spaces. The third line describes the availability times. In each line, the first number M_i (1 ≤ M_i ≤ 15) indicates the number of time ranges when the gates are available, followed by 2M_i non-negative integers (each not exceeding 10^9), separated by spaces. Each pair of numbers represents the start and end time of gate operation (time ranges do not overlap and are not required to be ordered).
The last two lines of the file contain the names of the planets between which the journey needs to be organized: from the planet specified in the penultimate line, where Alice is located, to the planet specified in the last line, where the congress is held.
It is known that the sum of the lengths of all lists of planets accessible through the gates does not exceed 100000.
Output
Output a single integer on one line: the minimum time in which Alice and her father can reach the congress if they start their journey at time 0. If it is impossible to reach the congress, output -1.