Maria the Traveler#6315

Maria the Traveler

2 seconds

256 megabytes

Hard

Maria Zelenchuk loved to travel. She could only travel when her father, the professor, took her along. One day, Professor Zelenchuk received an invitation to a conference on a very distant planet located at the other end of the galaxy. Since their spaceship, "Pegasus," was under repair, the professor decided to use public transportation—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 open 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.

After reviewing the schedule for the gates, the professor (who, let us recall, is a space zoologist) was overwhelmed. The journey would require many transfers and it was difficult to determine a route. He promised Maria she could go with him if she managed to find the shortest route to the conference. 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 per 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}$ M_i ( $1$ ≤ $M_{i}$ M_i ≤ $15$ ) indicates the number of time ranges when the gates are available, followed by $2 M_{i}$ 2M_i non-negative integers (each not exceeding $1 0^{9}$ 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 must be organized: from the planet specified in the penultimate line, where Maria is located, to the planet specified in the last line, where the conference will be 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 Maria and her father can reach the conference if they start their journey at time $0$ . If it is impossible to reach the conference, output $- 1$ .

Examples

Example 1