The subway consists of several subway lines. All metro stations in the city are numbered with natural numbers from 1 to N. There are several stations on each line. If the same station is located on several lines at once, then it is a transfer station and at this station you can transfer from any line that passes through it to any other (again, passing through it).
Write a program that, according to the description of the subway given to you, will determine with what minimum number of transfers you can get from station A to station B. If the given subway does not connect all the lines into one system, then it may turn out that it is impossible to get from station A to station B , in which case your program should determine it.
Input
First enter the number N — the number of metro stations in the city (2≤N≤100). This is followed by the number M — number of metro lines (1≤M≤20). Next comes the description of the M lines. The description of each line consists of the number P
i — the number of stations on this line (2≤P
i≤50) and P
i numbers specifying the numbers of stations through which the line passes (the line does not pass through any station twice ).
Then two different numbers are entered: A — starting station number, and B — the number of the station we need to get to. Moreover, if several lines pass through station A, then we can go down to any of them. Also, if several lines pass through station B, then it does not matter to us which line we arrive on.
Imprint
Print the minimum number of transfers we need. If it is impossible to get from station A to station B, the program should print a single number –1 (minus one).
Examples
| # |
Input |
Output |
| 1 |
5
2
4 1 2 3 4
2 5 3
3 1
| 0 |
| 2 |
5
5
2 1 2
2 1 3
2 2 3
2 3 4
2 4 5
15 |
2 |
| 3 |
10
2
6 1 3 5 7 4 9
6 2 4 6 8 10 7
38 |
1 |
| 4 |
4
2
2 1 2
2 3 4
1 3
| -1 |