Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Метро

(Время: 1 сек. Память: 16 Мб Сложность: 37%)

Метрополитен состоит из нескольких линий метро. Все станции метро в городе пронумерованы натуральными числами от 1 до N. На каждой линии расположено несколько станций. Если одна и та же станция расположена сразу на нескольких линиях, то она является станцией пересадки и на этой станции можно пересесть с любой линии, которая через нее проходит, на любую другую (опять же проходящую через нее).

Напишите программу, которая по данному вам описанию метрополитена определит, с каким минимальным числом пересадок можно добраться от станции A до станции B.

Входные данные

В первой строке входного файла INPUT.TXT записаны числа N и M – количество станций метро и количество линий метро соответственно (2 ≤ N ≤ 100, 1 ≤ M ≤ 20). Далее идет описание M линий. Описание каждой i-й линии записано в (i+1) строке, состоит из числа Pi – количества станций на этой линии (2 ≤ Pi ≤ 50) и Pi чисел, задающих номера станций, через которые проходит линия.

В последней строке записаны два целых числа A и B – номера начальной и конечной станций соответственно (1 ≤ A, B ≤ N, A ≠ B).

Выходные данные

В выходной файл OUTPUT.TXT выведите минимальное количество пересадок, которое нам потребуется. Если добраться от станции A до станции B невозможно, выведите в выходной файл одно число -1.

Примеры

INPUT.TXTOUTPUT.TXT
15 2
4 1 2 3 4
2 5 3
3 1
0
25 5
2 2 1
2 1 3
2 2 3
2 3 4
2 4 5
1 5
2
310 2
6 3 1 5 7 4 9
6 2 4 6 8 10 7
3 8
1
44 2
2 2 1
2 3 4
3 1
-1

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Школьный этап
 Муниципальный этап
 Региональный этап
 Полуфинал ВКОШП
 Личное первенство СФУ
 2007 / 2008 1 тур
 2007 / 2008 2 тур
 2007 / 2008 3 тур
 2008 / 2009 1 тур
 2008 / 2009 2 тур
 2008 / 2009 3 тур
 2009 / 2010 1 тур
 2009 / 2010 2 тур
 2009 / 2010 3 тур
 2010 / 2011 1 тур
 2010 / 2011 2 тур
 2010 / 2011 3 тур
 2011 / 2012 1 тур
 2011 / 2012 2 тур
 2011 / 2012 3 тур
 2012 / 2013 1 тур
 2012 / 2013 2 тур
 2012 / 2013 3 тур
 2013 / 2014 7-8 классы
 2013 / 2014 9-11 классы
 2014 / 2015 7-8 классы
 2014 / 2015 9-11 классы
 2015 / 2016 7-8 классы
 2015 / 2016 9-11 классы
 2016 / 2017 7-8 классы
 2016 / 2017 9-11 классы
 2017 / 2018 7-8 классы
 2017 / 2018 9-11 классы
 2018 / 2019 7-8 классы
 2018 / 2019 9-11 классы
 2019 / 2020 7-8 классы
 2019 / 2020 9-11 классы
 A. Hello world!
 B. Трафик
 C. Зелёный человечек
 D. НОЧД и НОНД
 E. Метро

Красноярский краевой Дворец пионеров, (c)2006 - 2020, E-mail: admin@acmp.ru