Задача Pcnet У корпорації «Роги та копита» є багато комп'ютерів (ПК) , ПК з'єднані в мережу та пронумеровано натуральними числами от 1 до N. У корпорації є кілька філій, у кожній – кілька комп’ютерів. Якщо один і той же комп’ютер належить кільком філіям, то це маршрутизатор (роутер), який може перенаправляти пакети, інформація може потрапити з однієї філії у будь-яку іншу, якщо маршрутизатор належить і їй. Напишіть програму, яка по даному опису мережі визначить, через яку мінімальну кількість маршрутизаторів інформація може дістатися із комп’ютера A на комп’ютер B (якщо хоч один із них чи обидва - маршрутизатори, вони в цю мінімальну кількість не входять, бо працюють в цьому випадку звичайними ПК). Якщо мережа пошкоджена, то може так трапитися, що із комп’ютера A на комп’ютер B інформація не потрапить. У цьому випадку ваша програма повинна на це вказати.

Технічні умови. Програма Pcnet читає з пристрою стандартного введення спочатку число N — кількість ПК у корпорації (2<=N<=100), та через пропуск M — кількість філій (1<=M<=20). Далі слідує опис M мереж кожної філії. Він складається з числа Pi — кількість ПК у цій філїї (2<=Pi <=50) і з Pi чисел, що задають номери ПК, увімкнутих у мережу (ніякий ПК не підключено двічі). В останньому рядку записано два різних числа: A — номер ПК, що передає інформацію, і B — номер ПК, на котрий інформація має потрапити. Якщо ПК A – маршрутизатор, то інформація може починати маршрут з будь-якої філії. Якщо ПК B - маршрутизатор - то байдуже, від якої філії прийде інформація. Програма виводить на пристрій стандартного виведення єдине число- мінімальну кількість маршрутизаторів (без початкового та кінцевого, якщо такі були). Якщо інформація з ПК A на ПК B потрапити не може, виведіть –1 (мінус один).

Приклади

Введення Виведення Введення Виведення Введення Виведення
5 2 0 5 5 2 4 2 -1
4 1 2 3 4   2 1 2   2 1 2  
2 5 3   2 1 3   2 3 4  
3 1   2 2 3   1 3  
    2 3 4      
    2 4 5      
    1 5      

 

© LIKT 1998-2018