Under construction

Still being built. Things may change

Minimum Transfer Route

Interview

Time limit1sMemory limit256 MB

Summary
Given several subway lines as sequences of stations, compute the minimum number of transfers to travel between two given stations using BFS over lines.
Level

Medium5 of 10

Topics
BFS, Graph, Implementation
Solved
No attempts yet

Problem

Given information about the subway lines in a city, write a program that finds the minimum number of transfers needed to travel from a starting station to a destination station. You do not need to output an actual route; output only the number of transfers.

Input

The first line contains the number of stations N (1 <= N <= 100,000) and the number of lines L (1 <= L <= 100,000).

Each of the next L lines lists, in order, the stations passed by one subway line. Each such line ends with -1.

The last line contains the starting station number and the destination station number. Station numbers are integers from 1 to N. The sum of the lengths of all subway lines does not exceed 1,000,000.

Output

Print the minimum number of transfers. If the destination cannot be reached, print -1.

Examples1

  1. Example 1

    Input
    10 3
1 2 3 4 5 -1
9 7 10 -1
7 6 3 8 -1
1 10
    Expected output
    2