Задача №510. Метро
Задачу «Метро» надо решать с помощью
std::setМетрополитен состоит из нескольких линий метро. Все станции метро в городе пронумерованы натуральными числами от 1 до \(N\). На каждой линии расположено несколько станций. Если одна и та же станция расположена сразу на нескольких линиях, то она является станцией пересадки и на этой станции можно пересесть с любой линии, которая через нее проходит, на любую другую (опять же проходящую через нее).
Напишите программу, которая по данному вам описанию метрополитена определит, с каким минимальным числом пересадок можно добраться со станции \(A\) на станцию \(B\). Если данный метрополитен не соединяет все линии в одну систему, то может так получиться, что со станции \(A\) на станцию \(B\) добраться невозможно, в этом случае ваша программа должна это определить.
Сначала вводится число \(N\) — количество станций метро в городе (2≤\(N\)≤100). Далее следует число \(M\) — количество линий метро (1≤\(M\)≤20). Далее идет описание \(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