Задача 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 одноразові квитки.