eolymp
bolt
Try our new interface for solving problems
Problems

Minibuses (RU)

Minibuses (RU)

В современном городе важную роль играют частные маршрутки. Известно количество городских маршрутов и общее число городских остановок. Через некоторые остановки может проходить несколько маршрутов, на которых, в случае необходимости, пассажир может совершать пересадки. Ваше задание очень простое: определить, с каким наименьшим количеством пересадок можно доехать от остановки \textbf{А} до остановки \textbf{В} . \textbf{Входные данные:} В первой строке задано \textbf{2} числа: количество остановок маршруток в городе \textbf{N} (\textbf{2}≤\textbf{N}≤\textbf{100000}) та количество маршрутов \textbf{М} (\textbf{1}≤\textbf{M}≤\textbf{20}). В последующих \textbf{М} строках указано количество остановок на соответствующем маршруте \textbf{K} (\textbf{2}≤\textbf{K_i}≤\textbf{50}) и перечислены сами номера остановок этого маршрута. В последней строке задано \textbf{2} числа -- номер остановки-отправления \textbf{А} и номер остановки -прибытия \textbf{В}. \textbf{Выходные данные:} Единственное число -- минимальное количество пересадок. В случае невозможности добраться от остановки \textbf{А} до остановки \textbf{B} пользуясь только маршрутками, выведите "\textbf{Call a taxi!}" (без кавычек).
Time limit 1 second
Memory limit 64 MiB
Input example #1
9 2
6 1 3 5 7 4 9
5 2 4 6 8 7
3 8
Output example #1
1