Задача №3108. Metro
Станции метро пронумерованы от 1 до n. Для каждой линии метро известно, какие станции на ней находятся. При этом станция называется пересадочной, если она находится как минимум на двух линиях. Даны номера начальной и конечной станций. Требуется определить, за какое наименьшее число пересадок можно доехать с одной станции до другой.
На вход программе сначала подается число n - количество станций метро в городе (2 <= n <= 200). Далее вводится число m — количество линий метро (1 <= m <= 100). Далее идет описание m линий. Описание каждой линии состоит из числа p_i — количества станций на этой линии (2 <= p_i <= 50) и p_i чисел, задающих номера станций, через которые проходит линия (ни через какую станцию линия не проходит дважды).
В конце вводятся два различных числа: A — номер начальной станции и B — номер станции, на которую нам нужно попасть. При этом если через станцию A проходит несколько линий, то мы можем спуститься на любую из них. Также если через станцию B проходит несколько линий, то нам неважно, по какой линии мы на нее приедем.
Выведите минимальное количество пересадок, которое нам понадобится. Если добраться со станции Aна станцию B, невозможно, то выведите одно число -1 (минус один).
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