| Codeforces Round 119 (Div. 1) |
|---|
| Закончено |
Zart PMP вышел в финал мирового чемпионата ICPC World Finals, который проводится в китайском городе Харбине. Сходив на групповую экскурсию в Sun Island Park и насладившись выставкой снежных скульптур, PMP должен вернуться к автобусам до того, как они уедут. Но парк очень большой, и он не знает, как найти стоянку.
В парке есть n перекрестков, пронумерованных от 1 до n. Есть m двунаправленных дорог, соединяющих некоторые пары из этих перекрестков. На k перекрестках волонтеры ICPC помогают командам и показывают им путь к месту назначения. Волонтеры стоят в фиксированных точках и не двигаются, никакие два волонтера не стоят на одном перекрестке.
Когда PMP просит волонтера указать путь до стоянки, тот/та может описать ему весь путь. Но парк полностью покрыт льдом и снегом и все выглядит почти одинаково. Из-за этого PMP может запомнить не более q перекрестков после каждого вопроса (не считая перекрестка, на котором он стоит в данный момент). Он всегда рассказывает волонтерам о своей слабой памяти и если нет прямого пути длиной не более q (в количестве дорог), ведущему к стоянке, то волонтер направит PMP к другому волонтеру (расстояние до которого в количестве дорог, разумеется, не должно превышать q). Волонтеры ICPC прекрасно знают парк и всегда указывают PMP самый лучший путь. Таким образом, если существует путь до стоянки, PMP безусловно найдет его.
Изначально PMP находится на перекрестке s, а автобусы стоят на перекрестке t. На перекрестке s всегда есть волонтер. Ваша задача — найти, при каком минимальном значении q PMP сможет найти автобусы.
В первой строке записаны через пробел три целых числа n, m, k (2 ≤ n ≤ 105, 0 ≤ m ≤ 2·105, 1 ≤ k ≤ n) — количество перекрестков, дорог и волонтеров соответственно. В следующей строке записано через пробел k различных целых чисел от 1 до n включительно — номера перекрестков, на которых стоят волонтеры.
Следующие m строк описывают дороги. В i-ой строке записаны через пробел два целых числа ui, vi (1 ≤ ui, vi ≤ n, ui ≠ vi) — два перекрестка, соединенные i-ой дорогой. Между любыми двумя перекрестками есть не более одной дороги.
Последняя строка входного файла содержит через пробел два целых числа s, t (1 ≤ s, t ≤ n, s ≠ t) — исходная позиция PMP, расположение автобусов. Не гарантируется, что автобусная станция достижима по дорогам парка из перекрестка с номером s.
Гарантируется, что на перекрестке s всегда стоит волонтер.
Выведите на единственной строке ответ к задаче: минимальное значении q, при котором PMP сможет найти автобусы. Если PMP не сможет найти автобусы ни при каком значении q выведите -1.
6 6 3
1 3 6
1 2
2 3
4 2
5 6
4 5
3 4
1 6
3
6 5 3
1 5 6
1 2
2 3
3 4
4 5
6 3
1 5
3
Первый пример проиллюстрирован ниже. Синим отмечены перекрестки, в которых находятся волонтеры. Пунктирная линия показывает возможный путь, для такого пути ответ q = 3:
Во втором примере, при q = 3 PMP может дойти до перекрестка номер 6, а потом дойти до автобусной остановки.
