Elevators

Time Limit: 10 Seconds Memory Limit: 131072 KB

The new building for the Computer Engineering department has several elevators, but has no stairs. In order to facilitate access to lecture rooms and offices, the manufacturer has set each elevator to stop only at certain pre-defined floors; like some elevators would only stop at odd floors and some only at even floors. But, things are more complicated than this and the buttons inside and outside of each elevator would only work for the set of floors that elevator is assigned to stop at. This has made some improvements in reaching certain destination floors, especially for the faculty members, but has caused a lot of confusions for people like students. If a person p is at floor i and wants to go to floor j, which elevator should p take, and to which elevator(s) and on which floor(s) should (s)he transfer to, so that p reaches floor j with minimum travel time? We define p’s travel path as i = f1 → f2 → · · · → fk = j, then p’s travel time that we want to minimize is .You have been asked to write an application to help people using these elevators.

Input

There are multiple test cases in the input. The first line of each test case specifies n (1 ⩽ n ⩽ 10), the number of elevators, followed by the source and destination floors. The i-th line (1 ⩽ I ⩽ n) of the next n lines starts with mi (2 ⩽ mi ⩽ 150), the number of floors at which the i-th elevator may stop, followed by a list of mi non-negative floor numbers (all numbers are less than 150). The input terminates with a line containing 0 0 0 which should not be processed.

Output

For each test case, output a line containing the minimum travel time that one needs to reach the destination floor when starting from the source floor. It is guaranteed that there is always a possible way from the source floor to the destination floor.

Sample Input

2 2 5
5 0 1 3 5 7
5 0 2 4 6 8
3 3 8
6 0 1 2 3 4 5
5 0 6 7 8 9
4 0 4 5 6
0 0 0

Sample Output

7
5

Submit

Source: Tehran, Asia Region - Regional 2014