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.
Input
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
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.
Sample
input | output |
---|
7
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 | 7 |
Problem Author: Eugeniy Krokhalev (idea by Aleksandr Klepinin)
Problem Source: IX Collegiate Students Urals Programming Contest. Yekaterinburg, April 19-24, 2005