ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

Ural Championship 2005 Round II

About     Problems     Submit solution     Judge status     Standings
Contest is over

B. Spaceology vs. Chronistics

Time limit: 1.0 second
Memory limit: 64 MB
Every year in the city of Radon-Snark a famous symposium of scientists-spaceologists is held.
Professor A, haunter of the symposium, has decided this time to invite professor B, who does research in the adjacent field of science, applied chronistics.
Unfortunately, professor A has forgotten to meet professor B at the railway station (he was thinking about the exciting future of spaceology and remembered that his friend was coming only when B had already arrived at the city). "There's nothing left to do, I have to go", decided A. He got into his spacemobile and left to the railway station.
Now the world-famous scientist B can't wait even a second (chronistics think that only real action is true, not the some vague argumentation). He has got into his chronomobile immediately, and has left the railway station (A and B have started at the same time). What's left to do is to find out when A would meet B. Note that the spacemobile and chronomobile would not stop before they meet.
Remember that the symposium is just about to start and the strange things that are always associated with the symposium already began to happen. While notable scientists discuss their problems, all the machinery in the city behaves very strange. For example, all the spacemobiles turn to the leftmost road on each junction, and the chronomobiles turn to the rightmost one. Also, leaving the vehicle on the road between two junctions is against the law, so A and B can only meet each other on a junction.


The first line contains one number N (N ≤ 100000) that is the amount of junctions in the city of Radon-Snark. The following N lines describe the junctions. The (i + 1)st line contains a list of junctions that can be reached from the ith junction directly. The roads are listed in order from the leftmost to the rightmost. All roads enter to a junction only from one side, that's why words "leftmost" and "rightmost" have sense. The list is terminated with zero. Each list contains at least one nonzero number. The list can contain a road connecting a junction with itself.
The last input line contains two numbers. The first one specifies the junction where A starts the trip in his spacemobile. The second number is the junction where B starts from.


Output the number of minutes that B will need to meet A. It takes exactly one minute to travel from one junction to another directly reachable junction. Output −1 if they won't meet.


2 4 0
3 1 0
4 2 0
5 1 6 3 0
6 4 0
2 5 4 0
6 0
1 7
Problem Author: Eugeniy Krokhalev (idea by Aleksandr Klepinin)
Problem Source: IX Collegiate Students Urals Programming Contest. Yekaterinburg, April 19-24, 2005
To submit the solution for this problem go to the Problem set: 1361. Spaceology vs. Chronistics