Метро
(Время: 1 сек. Память: 16 Мб Сложность: 37%)
Метрополитен состоит из нескольких линий метро. Все станции метро в городе пронумерованы натуральными числами от 1 до N. На каждой линии расположено несколько станций. Если одна и та же станция расположена сразу на нескольких линиях, то она является станцией пересадки и на этой станции можно пересесть с любой линии, которая через нее проходит, на любую другую (опять же проходящую через нее).
Напишите программу, которая по данному вам описанию метрополитена определит, с каким минимальным числом пересадок можно добраться от станции A до станции B.
Входные данные
В первой строке входного файла INPUT.TXT записаны числа N и M – количество станций метро и количество линий метро соответственно (2 ≤ N ≤ 100, 1 ≤ M ≤ 20). Далее идет описание M линий. Описание каждой i-й линии записано в (i+1) строке, состоит из числа Pi – количества станций на этой линии (2 ≤ Pi ≤ 50) и Pi чисел, задающих номера станций, через которые проходит линия.
В последней строке записаны два целых числа A и B – номера начальной и конечной станций соответственно (1 ≤ A, B ≤ N, A ≠ B).
Выходные данные
В выходной файл OUTPUT.TXT выведите минимальное количество пересадок, которое нам потребуется. Если добраться от станции A до станции B невозможно, выведите в выходной файл одно число -1.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 5 2
4 1 2 3 4
2 5 3
3 1 | 0 |
| 2 | 5 5
2 2 1
2 1 3
2 2 3
2 3 4
2 4 5
1 5 | 2 |
| 3 | 10 2
6 3 1 5 7 4 9
6 2 4 6 8 10 7
3 8 | 1 |
| 4 | 4 2
2 2 1
2 3 4
3 1 | -1 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
