всесиб 5

/*Задача 5. Вадим и город Е
Имя входного файла: input.txt
Имя выходного файла: output.txt
Ограничение по времени: 1 секунда, для Java — 2 секунды
Ограничение по памяти: 512 мегабайт
После того, как Вадим переехал из города N в город E, за ним стали охотиться фанаты.
Вадим — человек занятой, поэтому не хочет тратить свое время на диалоги. Но если так
случится и фанат его встретит, то Вадим не сможет отказаться от диалога с ним.
E — город из нескольких площадей, соединенных между собой улицами таким образом,
что для каждой пары площадей, соединенных улицей, существует не более одного другого
пути, связывающего эти площади. При этом между любыми двумя площадями существует
путь. Особенность проектирования города Е заключается в том, что начав свой
путь с любой площади и обойдя три другие различные, невозможно вернуться
на начальную площадь по другой улице напрямую.
В самом начале Вадим находится на площади с номером 1, а фанаты на площадях 𝑎1 · · · 𝑎𝑘.
Перебежать с одной площади на другую возможно, только если они соединены улицей. За
один шаг Вадим перебегает на соседнюю площадь, только после этого на свои соседние
площади перебегают фанаты, после чего снова перебегает Вадим, после него фанаты, и так
далее. Ни Вадим, ни фанаты не могут остаться на текущей площади. Если хотя бы один из
фанатов окажется с Вадимом на одной площади, то Вадиму придется общаться с ними.
Может ли Вадим бегать от своих преследователей таким образом, чтобы они его никогда
не поймали?
Формат входных данных
В первой строке входного файла записаны три целых числа 𝑁, 𝑀, 𝐾 —
количество площадей, количество улиц и количество фанатов, ищущих Вадима
(2 6 𝑁 6 2 · 105
, 𝑁 − 1 6 𝑀 6 106
, 0 6 𝐾 6 100).
Во второй строке заданы 𝐾 чисел 𝑎𝑖 — номера площадей, на которых находятся фанаты
изначально (2 6 𝑎𝑖 6 𝑁, 1 6 𝑖 6 𝐾). Строка пустая, если 𝐾 = 0.
В последних 𝑀 строках записано по два числа — номера площадей 𝑢, 𝑣, связанных дорогой (1 6 𝑢, 𝑣 6 𝑁; 𝑢 ̸= 𝑣).
Между любыми двумя площадями существует не более одной улицы.
Формат выходных данных
В выходной фал необходимо вывесит слово YES, если Вадим может бесконечно бегать по
городу E от фанатов, иначе нужно вывести слово NO.
Система оценки
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.
Подзадача Баллы Ограничения Необходимые подзадачи
1 0 Тесты из условия
2 20 0 6 𝐾 6 2; 2 6 𝑁 6 100 1
3 30 0 6 𝐾 6 2; 2 6 𝑁 6 1000 1, 2
4 50 Нет дополнительных ограничений 1, 2, 3
Страница 10 из 14
Всесибирская открытая олимпиада школьников по информатике
Отборочный очный этап, 9-11 классы, 27 ноября 2022 г.
Примеры
input.txt output.txt
5 5 1
2
1 2
2 3
3 4
4 5
5 1
YES
5 5 2
4 5
1 2
2 3
3 4
4 5
5 1
NO
*/