Погоня в Пустоте
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Логан и Дэдпул пытаются сбежать от Алиота в Пустоте. Алиот, похожий на облако, может занимать произвольное пространство и распространяться в любом направлении по поверхности Пустоты.

Пустота состоит из $$$n$$$ локаций, пригодных для жизни (с натяжкой). Герои находятся в локации $$$1$$$, а вход в укрытие расположен в локации $$$n$$$. Аолиот уже проник в $$$k$$$ локаций $$$a_1, \ldots, a_k$$$, причем известно, что его нет в локации с героями и локации с укрытием.

Также между какими-то локациями есть пути или тоннели — всего их $$$m$$$ штук, и $$$i$$$-й из них соединяет локации $$$x_i$$$ и $$$y_i$$$. По каждому такому пути можно за одинаковое время переместиться с одной локации на другую в любом направлении.

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

Если герои и Алиот точно окажутся в одной локации одновременно, выведите, что для них нет спасения. Также учтите, что Алиот именно «распространяется», а не перемещается — при его движении в новую локацию, старая локация также остается занятой им.

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

В первой входных данных даны три целых числа $$$n$$$, $$$m$$$ и $$$k$$$ — число локаций в Пустоте, число построенных между локациями тоннелей и число локаций, занятых Алиотом ($$$3 \le n \le 10^5$$$; $$$1 \le m \le 2 \cdot 10^5$$$; $$$1 \le k \le n - 2$$$).

Во второй строке входных данных перечислены $$$k$$$ целых чисел $$$a_i$$$ — номера локаций, занятых Алиотом ($$$2 \le a_i \le n - 1$$$).

В следующих $$$m$$$ строках дано описание тоннелей, построенных между локациями. Описание тоннеля состоит из двух чисел $$$x_i$$$ и $$$y_i$$$ — номеров локаций, которые этот тоннель соединяет ($$$1 \le x_i, y_i \le n$$$; $$$x_i \neq y_i$$$).

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

Выведите ответ на задачу — наибольшее общее число тоннелей между локациями, при котором герои успеют добраться до убежища, не встретившись с Алиотом.

Если у героев нет шансов не побег вне зависимости от того, сколько тоннелей будет достроено к уже имеющимся, вместо этого выведите $$$-1$$$.

Примеры

Входные данные
3 1 1
2
1 3
Выходные данные
1
Входные данные
7 6 3
5 6 2
1 7
6 2
1 4
3 6
5 3
2 1
Выходные данные
12
Входные данные
4 5 1
3
1 4
3 4
4 2
1 3
3 2
Выходные данные
-1