Олимпиады по программированию

olympiads.ru

Олимпиады прошлых лет
2020/21
2019/20
2018/19
2017/18
2016/17
2015/16
2014/15
2013/14
2012/13
2011/12
2010/11
2009/10
2008/09
2007/08
2006/07

IV открытая олимпиада школьников по программированию (2009/10)
Доска объявлений олимпиады
Информация об олимпиаде
Заключительный этап
Информация о заключительном этапе
Список приглашенных
Результаты заключительного этапа
Задачи, тесты
Персональные странички участников
Предварительное раписание
Система оценки решений на заключительном этапе
Информация для иногородних участников
Планируемое размещение иногородних
Как добраться
Заочный этап
Задачи, тесты
Регистрация
1 тур
Персональная страничка участника
Текущие результаты
2 тур
Персональная страничка участника
Текущие результаты
Примеры реализации ввода-вывода на разных языках
FAQ по работе с тестирующей системой
Связаться с оргкомитетом

Олимпиада проводится при поддержке Московского физико-технического института, Компьютерной компании НИКС, Компании Yandex

Информационная поддержка:
журнал "Мир ПК"

IV Открытая олимпиада школьников по программированию, 2009/10 учебный год

Задача G. Эвакуация

Имя входного файла: g.in
Имя выходного файла: g.out
Максимальное время работы на одном тесте: 1 секунда
Максимальный объем используемой памяти: 64 мегабайта

Одна из Сверхсекретных организаций, чье название мы не имеем право разглашать, представляет собой сеть из N подземных бункеров, соединенных равными по длине туннелями, по которым из любого бункера можно добраться до любого другого (не обязательно напрямую). Связь с внешним миром осуществляется через специальные засекреченные выходы, которые расположены в некоторых из бункеров.

Организации понадобилось составить план эвакуации персонала на случай экстренной ситуации. Для этого для каждого из бункеров необходимо узнать, сколько времени потребуется для того, чтобы добраться до ближайшего из выходов. Вам, как специалисту по таким задачам, поручено рассчитать необходимое время для каждого из бункеров по заданному описанию помещения Сверхсекретной организации. Для вашего же удобства бункеры занумерованы числами от 1 до N.

Формат входных данных

Сначала вводятся два натуральных числа N, K (1 ≤ N ≤ 100000, 1 ≤ K ≤ N) - количество бункеров и количество выходов соответственно. Далее через пробел записаны K различных чисел от 1 до N, обозначающих номера бункеров, в которых расположены выходы. Потом идёт число M (1 ≤ M ≤ 100000) - количество туннелей. Далее вводятся M пар чисел - номера бункеров, соединенных туннелем. По каждому из туннелей можно двигаться в обе стороны. В организации не существует туннелей, ведущих из бункера в самого себя, зато может существовать более одного туннеля между парой бункеров.

Формат выходных данных

Выведите N чисел, разделенных пробелом - для каждого из бункеров минимальное время, необходимое чтобы добраться до выхода. Считайте, что время перемещения по одному туннелю равно 1.

Примеры

g.in g.out
3
1
2
3
1 2
3 1
2 3
1 0 1
10
2
10 8 
9
6 7
7 5
5 8
8 1
1 10
10 3
3 4
4 9
9 2
1 4 1 2 1 3 2 0 3 0