1. Задача METRO (20 балів)

Ім’я вхідного файлу: METRO.DAT

Ім’я вихідного файлу: METRO.SOL

Максимальний час роботи на одному тесті: 20с

Метрополітен складається з декількох ліній метро. Усі станції метро в місті пронумеровані натуральними числами від 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 (мінус один).

Приклад

2. Задача “Школи” (100 балів)

Ім’я вхідного файлу: S.DAT

Ім’я вихідного файлу: S.SOL

Максимальний час роботи на одному тесті: 20с

З метою підготовки до проведення олімпіади з інформатики мер вирішив забезпечити надійним електропостачанням всі школи міста. Для цього потрібно провести лінію електропередач від альтернативного джерела електроенергії "ЕНЕРГЕТИК" до однієї з шкіл (не має значення до якої), а також з'єднати лініями електропередач деякі школи між собою. Вважається, що школа має надійне електропостачання, якщо вона напряму з’єднана з "ЕНЕРГЕТИК", або з однією з шкіл, яка має надійне електропостачання.

Відома вартість з’єднань між деякими парами шкіл. Мер міста вирішив обрати одну з двох найекономніших схем електропостачання (вартість схеми дорівнює сумі вартостей з’єднань пар шкіл).

Складіть програму SCHOOLS, яка обчислює вартість двох найекономічніших схем альтернативного енергопостачання шкіл.

Формат вхідних даних

У першому рядку вхідного файлу S.DAT розташовані два натуральних числа, відокремлених пропусками: N (3 ≤ N ≤ 100), кількість шкіл в місті, та M - кількість можливих з’єднань між ними. В кожному з наступних M рядків знаходяться по три числа: Ai, Bi, Ci, відокремлених пропусками, де Ci - вартість прокладання лінії електропостачання (1 ≤ Ci ≤ 300) від школи Ai до школи Bi (i=1,2,…,N).

Формат вихідних даних

В єдиному рядку вихідного файлу S.SOL мають міститись два натуральних числа S1 та S2, відокремлених пропусками – дві найменші вартості схем (S1≤S2). S1=S2 тільки тоді, коли існує декілька варіантів схем надійного електропостачання найменшої вартості.

Приклад