Zadanie

Isté víťazstvo

Počet bodov: 50

Eliška obľubuje ázijskú kuchyňu natoľko, že sa v jedno nudné ráno rozhodla pripraviť si na obed fritovaného pavúka. Veľkého stromového pavúka. Keďže takýto pokrm ešte nevarila, začala zisťovať, ako sa to robí.

Od Naďky sa dozvedela, že takého pavúka treba najskôr oholiť. Prirodzene, ináč by to bolo ako jesť vlasy. Dodala však, že niektoré časti pavúka sa nesmú holiť, pretože sú v nich jedové žľazy, ktoré by sa tým narušili a jed by mohol kuchárke Eliške vyšplechnúť do očí.

Eliška doma našla iba starú tupú žiletku, ktorá zvládne spraviť už iba jeden súvislý hol.

V tom Eliške v hlave skrsol plán. O oholenie pavúka poprosí Adama. Vymyslí si, že nemá dosť sily na holenie. Ukáže mu, aký hol má spraviť. Samozrejme, tento hol musí ísť cez všetky časti stromového pavúka, ktoré obsahujú jed. Adam tak určite aspoň pár hodín nebude vidieť a Eliška na celoštátku Zenitu vyhrá obe kategórie!

Adam nie je hlúpy. Bolo by mu podozrivé, keby Eliška chcela jeden konkrétny hol a žiadny iný. Eliška sa teda rozhodla, že mu dá na výber z niekoľkých holov. Finta bude v tom, že každý z nich bude prechádzať všetkými jedovatými časťami stromového pavúka. Pre istotu.

Koľko holov ponúkne Eliška Adamovi, ak mu ponúkne všetky vyhovujúce? Dva holy považujeme za rôzne, ak ich množiny začiatočného a konečného vrchola sú rôzne. Holy z 1 do 4 a zo 4 do 1 sú teda rovnaké, avšak z 2 do 6 a zo 6 do 1 sú rôzne.

Vstup

V prvom riadku vstupu sú čísla \(n\) – počet vrcholov pavúka a \(k < n\) – počet jeho jedovatých hrán.

Nasleduje \(n - 1\) riadkov. Na \(i\)-tom z nich sú čísla \(1 \leq a, b \leq n\) – čísla vrcholov pavúka, ktoré sú spojené hranou. Pavúk je súvislý.

Na poslednom riadku vstupu je \(k\) medzerou oddelených čísiel – indexy hrán zo vstupu, ktoré sú jedovaté a teda ich treba oholiť jedným súvislým holom. Indexy hrán začínajú na 0.

Sú 3 sady vstupov. V nich naviac platia nasledovné obmedzenia:

Výstup

Na jediný riadok výstupu vypíšte jedno číslo – počet možností, ktoré Eliška ponúkne Adamovi.

Príklady

Input:

3 1
3 2
1 2
1

Output:

2

Eliška ponúkne Adamovi holy z 1 do 2 a z 1 do 3. Hol z 1 do 2 je rovnaký, ako hol z 2 do 1, preto hol z 2 do 1 už nepočítame. Z rovnakého dôvodu nepočítame hol z 3 do 1.

Input:

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

Output:

0

Neexistuje tu žiaden hol (cesta), ktorý by oholil všetky jedovaté hrany.