Tram

Interview

Time limit1sMemory limit128 MB

Summary

Find the minimum number of switch changes needed to travel from intersection A to B in a directed graph where each node's first listed edge is free and others cost 1, using shortest-path with 0/1 edge weights.

Level: Medium5 of 10
Topics: Shortest path, Graph, BFS
Solved: No attempts yet

Problem

A tram network has intersections connected by rails. At every intersection, a switch initially points to one of the outgoing rails. When a tram enters an intersection, it can leave only along the rail currently selected by that switch. To leave through any other outgoing rail, the driver must manually change the switch.

For a trip from intersection A to intersection B, the driver wants a route that minimizes the number of manual switch changes.

Compute the minimum number of switch changes needed to travel from A to B.

Input

The first line contains three integers N, A, and B separated by spaces. N is the number of intersections, and the intersections are numbered from 1 to N.

2 <= N <= 100
1 <= A, B <= N

Each of the next N lines describes the outgoing rails from one intersection. The i-th of these lines begins with an integer K_i (0 <= K_i <= N - 1), the number of outgoing rails from intersection i. It is followed by K_i integers, the intersections that can be reached directly from intersection i.

If K_i > 0, the switch at intersection i initially points to the first listed intersection.

Output

Print one integer: the minimum number of manual switch changes needed to travel from A to B.

If there is no route from A to B, print -1.

Examples3

Example 1
Input
```
3 2 1
2 2 3
2 3 1
2 1 2
```
Expected output
```
0
```
Example 2
Input
```
3 1 3
1 2
2 1 3
1 2
```
Expected output
```
1
```
Example 3
Input
```
4 4 2
1 2
1 1
1 4
1 3
```
Expected output
```
-1
```