406877: GYM102591 E Данияр и его любимые магазины
Description
Во время карантина Данияру стало очень скучно, и теперь, чтобы проветриться, он решил походить по своим любимым магазинам.
В городе $$$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