406877: GYM102591 E Данияр и его любимые магазины

E. Данияр и его любимые магазиныограничение по времени на тест2.0 sограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный вывод

Во время карантина Данияру стало очень скучно, и теперь, чтобы проветриться, он решил походить по своим любимым магазинам.

В городе $$$N$$$ перекрестков. Перекрестки пронумерованы числами от $$$1$$$ до $$$N$$$. Между этими перекрестками расположены $$$M$$$ двусторонних дорог. Во время карантина нельзя свободно перемещаться, для того чтобы проехать по какой-то дороге, нужно иметь специальный пропуск для этой дороги. Данияр живет на перекрестке $$$1$$$. У него $$$K$$$ любимых магазинов, расположенных на перекрестках $$$A_1,A_2,..,A_K$$$. Получения одного пропуска занимает очень много времени, поэтому Данияр хочет узнать какое минимальное количество пропусков ему необходимо, чтобы он мог свободно передвигаться между своим домом и любимыми магазинами. Помогите ему.

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

В первой строке находятся три целых числа $$$N,M$$$ и $$$K(1 \le N,M \le 10^5, 1 \le K \le 4)$$$.

Во второй строке находятся $$$K$$$ целых числа $$$A_1,A_2,..,A_K(1 \le A_i \le N)$$$.

В следующих $$$M$$$ строках находятся по два целых числа $$$U_i,V_i(1 \le U_i , V_i \le N, U_i \ne V_i)$$$ — означающая, что есть дорого между двумя этими перекрестками.

Гарантируется, что граф связный, то есть от каждого перекрестка можно добраться до каждого другого перекрестка. Между каждой парой перекрестков проходит не более одной дороги.

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

Выведите минимальное количество пропусков необходимое Данияру.

ПримерыВходные данные

6 7 2
2 3
1 5
1 6
3 5
3 4
2 4
3 6
2 6

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

3

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

4 3 3
1 3 3
1 2
2 3
3 4

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

2