Задача Travel2018. У великому місті всі мешканці  їздять лише автобусами. Жителі вимушені витрачати час, економлячи гроші -  одноразові квитки дорогі. Тому пасажири намагаються планувати поїздки так, аби пересідати з маршруту на інший як можна  меншу кількість разів. Добре, що в місті на кожній зупинці висить розклад руху автобусів по всім маршрутам. Напишіть програму, яка допоможе доїхати з однієї вибраної зупинки на іншу, використовуючи мінімальну кількість одноразових квитків.

 Технічні умови. Програма Travel2018 читає з стандартного пристрою введення у першому рядку чотири цілих числа, розділені пропусками: кількість автобусів N, кількість зупинок у місті M, число A – зупинка, де пасажир починає поїздку і число В - зупинка, куди хоче доїхати пасажир. Автобуси нумеруються від 1 до N, зупинки - від 1 до M ( 1 ≤ N ≤ 1000; 1 ≤ M ≤ 1000; 1 ≤ A, B ≤ M; A ≠ B.) Наступні М рядків містять списки зупинок автобусів. (i +1) -й рядок  описує i-ту зупинку: перше ціле число Li (1 ≤ Li ≤ N) - кількість автобусів, що зупиняються на ній, а далі Li цілих чисел, розділених пропусками - номери маршрутів цих автобусів. Гарантується, що розв’язок існує. Програма виводить на стандартний пристрій виведення одне ціле число K - мінімальна кількість одиночних квитків, щоб доїхати від А до B

Приклад

Введення

4 9 1 8

2 1 2

2 2 3

1 1

3 1 2 3

1 3

2 3 4

1 3

1 4

1 2

Виведення

3

Коментар. Сідаємо в автобус №2,їдемо до зупинки 2, потім на автобусі №3. їдемо до зупинки 6 і на автобусі № 4 доїжджаємо зупинки 8. Це не єдиний спосіб досягти мети,  використовуючи лише 3 одноразові квитки.

© LIKT 1998-2018