Time limit 1000/4000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb.
Problem description
Istanbul is a great city with high concentration of important historic buildings like Blue Mosque, Haghia Sophia, Topkapi Palace etc. It connects Europe and Asia and divided into two parts with Bosphorus which connects the Sea of Marmara and the Black Sea. There is something to be seen in any time of year.
That's why tourists from all over the world come to visit this city. There are a lot of types of public transport: Metro, Metrobus, Seabus, Dolmush... During the expedition tourists often have to change transport and as a result they spend quite a lot money just to get to the place they wish.
There are N stops and M vehicles in the city. Every vehicle has its own route that visits some stops. If two routes have same stop then you can change vehicle at that stop. According to the information about vehicles calculate how many times at least you will have to change vehicle to get from stop A to stop B if it's possible.
Input
Line 1: A single integer N (2 ≤ N ≤ 100).
Line 2: A single integer M (1 ≤ M ≤ 20).
Line 3..M+2: Each line starts with Pi (2 ≤ Pi ≤ 50) - number of stops on this vehicle and follows by Pi integers - stop idetifiers.
Line M+3: Two different integers A and B.
Output
Write the minimum number of vehicle changes or -1 if there is no route.
Example
| stdin |
stdout |
5
2
4 1 2 3 4
2 5 3
3 1 |
0 |
5
5
2 1 2
2 1 3
2 2 3
2 3 4
2 4 5
1 5
|
2 |
10
2
6 1 3 5 7 4 9
6 2 4 6 8 10 7
3 8
|
1 |
4
2
2 1 2
2 3 4
1 3
|
-1 |
Для отправки решений необходимо выполнить вход.
|