7. Lamborghini? Bicykel!

22.02.2022, Amsterdam.

Presne pred rokom Kolektív Sofistikovaných Pesimistov získal 90%-nú väčšinu Klimatizovaného Svetového Parlamentu.

Dnes organizuje tajnú Konferenciu o Sprevinilej Planéte, ktorej cieľom je rozhodnúť o osude našej modrej planéty Zem. Iniciatíva na zvolanie tejto tajnej konferencie bola podaná po zverejnení virálnej eseje šéfa zmieneného kolektívu, Dr. Michala Anderleho, s názvom “Ľudstvo, ktoré si zvolilo pesimistov, stráca nárok na budúcnosť”. Logicky, v kolektíve teraz prevláda názor, že Zem treba odpáliť do vesmíru a/alebo zrovnať so zemou.

Je tu však nádej. Posledný optimista. Posledný pravý optimista, s vôľou zachrániť túto planétu pred nenávratnou skazou. Jeho meno je Askar.

vŕŕŕŕŕ Somebody once told me vŕŕŕŕŕ the world is gonna roll me vŕŕŕŕŕ

Úloha

Askar sa musí dostať zo svojho domu na Konferenciu o Sprevinilej Planéte a spraviť tam niečo bombové.

Mapa mesta je neorientovaný graf s \(n\) vrcholmi, očíslovanými \(1, 2, \dots, n\). Vo vrchole \(1\) je Askarov dom a vo vrchole \(n\) sa organizuje konferencia. V niektorých vrcholoch sa nachádzajú bike-sharing stanice. V nich je možnosť nasadnúť na bicykel, alebo ho odložiť a pokračovať pešo. Nikde inde nemožno získať ani odložiť bicykel.

Keď sa Askar hýbe pešo, po jednej hrane prejde za \(k\) minút. Na bicykli to zvláda za \(1\) minútu. Doma bicykel nemá a do budovy konferencie tiež nemôže prísť s bicyklom.

Zistite, koľko minút mu bude trvať, kým dostane šancu zachrániť našú krásnu planétu.

Formát vstupu

Na prvom riadku sa nachádzajú dve kladné celé čísla \(n\) a \(k\) – počet vrcholov grafu a čas, ktorý Askarovi trvá prejdenie jednej hrany pešo.

Na druhom riadku sa nachádza jedno celé číslo \(m\) – počet hrán v grafe.

Každý z nasledujúcich \(m\) riadkov obsahuje dve čísla: \(a_i\), \(b_i\) (\(1 \leq a_i, b_i \leq n\)), ktoré hovoria, že medzi vrcholmi \(a_i\) a \(b_i\) je hrana. Medzi každou dvojicou vrcholov je najviac jedna hrana. Môžete predpokladať, že zo štartu sa dá dostať do každého iného vrcholu postupnosťou hrán.

Na ďalšom riadku je jedno celé číslo \(s\) – počet bike-sharing staníc.

Každý z nasledujúcich \(s\) riadkov obsahuje jedno číslo \(s_i\), ktoré hovorí, že vo vrchole \(s_i\) sa nachádza stanica. Tieto čísla sú rôzne a platí \(1 < s_i < n\).

Formát výstupu

Vypíšte jeden riadok a na ňom jedno číslo – najmenší počet minút, za ktorý sa Askar vie dostať z domu do budovy konferencie.

Hodnotenie

Sú štyri sady vstupov. Platí pre ne nasledovné:

Vo všetkých vstupoch \(1 < k \leq 10^5\). Navyše, pri práci s časovými a pamäťovými zložitosťami môžete predpokladať, že \(O(k) = O(n)\).

Príklad

Input:

5 10
4
1 3
3 4
5 4
2 1
2
2
4

Output:

23

Askar najprv prejde za desať minút hranu do vrcholu \(2\). Vo vrchole \(2\) nasadne na bicykel. Za tri minúty to odbicykluje do vrcholu \(4\), kde bicykel nechá a za ďalších desať minút už dorazí na miesto konferencie.