1072:Bus Transfer

Time/Memory Limit:1000 MS/32768 K
Submitted:Accepted: 7

 Problem Description

Recently,Tong is going to FZ city to find his girlfriend. In the FZ,he had to take bus to there where his girlfriend in.In order to be convenient,he want to change bus as less times as possible.Now give you the some bus route,You want to calculate the minimum times of the bus changing.

 Input

The input consists of multiple test cases.Each case contains four integer N,M(1<=N,M<=20),S,T(1<=S,T<=M), the first value indicated the number of ths bus,the second value M indicated the number of bus station,S and T respectivelyindicated his and his grilfriend's current bus station.Then N lines follow,represented the n bus route information.Each contains an integer D,indicated the number of the bus station,then follow D bus stations.The bus station number with 1~M.

 Output

For each case, output the minimum times of the bus changing in one line.

 Sample Input

3 5 1 5
3 1 2 3
4 2 3 4 5
3 1 2 5
7 7 1 7
2 1 2
2 2 3
2 3 4
2 4 5
2 5 7
2 5 6
2 6 7

 Sample Output

0
4

 Author

jwt

 Recommend

zh