Minimum Switch Toggles in a Tram Network

In a magical town, there is a special tram network consisting of several intersections and tracks. Each intersection has several outgoing tracks and a switch controlling which track is used. The switch has a default state that points to one of the outgoing tracks. When a tram reaches an intersection, it will automatically take the default track. However, if the driver wishes to take a route other than the default, they must get off and toggle the switch.

Your task is to determine the minimum number of switch toggles needed to travel from intersection \(A\) to intersection \(B\).

The network is described as follows. Each intersection \(i\) (1-indexed) has a list of outgoing tracks. The first track in the list is the default track (cost 0) and every other track requires a toggle (cost 1). If there is no available route from \(A\) to \(B\), output -1.

Note: The cost to use an edge is \(0\) if it is the default track and \(1\) if it is not.

inputFormat

The first line contains three integers \(A\), \(B\) and \(n\) where \(A\) is the starting intersection, \(B\) is the destination intersection, and \(n\) is the number of intersections. The intersections are numbered from 1 to \(n\).

Then \(n\) lines follow. The \(i\)-th line describes intersection \(i\) as follows: it starts with an integer \(k\) (the number of outgoing tracks), followed by \(k\) integers representing the destination intersections of each track. The first destination is the default track (with cost 0) and the remaining tracks, if any, each incur a cost of 1 when chosen.

You may assume that \(1 \leq A, B \leq n\) and \(k \ge 0\).

outputFormat

Output a single integer: the minimum number of switch toggles required to go from intersection \(A\) to intersection \(B\). If \(B\) is not reachable from \(A\), output -1.

sample

1 3 3
2 2 3
1 3
1 1

0