Fişierul intrare/ieşire:	bile7.in, bile7.out	Sursă	Selectie echipe ACM ICPC, UPB 2009
Autor	Mugurel Ionut Andreica	Adăugată de	Mugurel-Ionut Andreica •mugurelionut
Timp execuţie pe test	0.05 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Bile7

Se da un arbore cu N noduri, numerotate de la 1 la N. Radacina arborelui este nodul 1. In nodul P se afla o bila albastra. In fiecare din celelalte noduri se afla ori o bila rosie, ori nicio bila. Se doreste eliberarea tuturor nodurilor de pe drumul de la nodul P la radacina arborelui. Mai exact, trebuie sa mutam unele bile rosii, astfel incat in fiecare nod de pe drumul de la nodul P la nodul 1 (cu exceptia nodului P) sa nu se afle nicio bila. O mutare consta in a lua o bila rosie dintr-un nod x si a o amplasa intr-un nod y care este fiu al lui x, cu conditia ca nodul y sa fie liber (adica sa nu contina nicio bila, fie ea rosie sau albastra). Bila albastra nu se poate muta din nodul P.

Determinati numarul minim de mutari necesare pentru ca niciunul din nodurile de pe drumul de la nodul P la nodul 1 sa nu contina vreo bila rosie.

Date de intrare

Prima linie a fisierului bile7.in contine numerele intregi N, P si K. K reprezinta numarul total de bile rosii ce se afla in nodurile arborelui. Urmatoarele N linii descriu structura arborelui: a i-a dintre aceste linii contine numarul nfii(i), urmat de nfii(i) numere f₁, ..., f_nfii(i), avand semnificatia ca nodurile f₁, ..., f_nfii(i) sunt fiii nodului i. Ultima linie contine K numere intregi, reprezentand numerele nodurilor in care se afla cate o bila rosie. Toate numerele de pe aceeasi linie sunt separate prin cate un spatiu.

Date de ieşire

In fisierul de iesire bile7.out veti afisa numarul minim de mutari cerut. Daca nu exista nicio secventa de mutari care sa indeplineasca cerintele problemei, afisati numarul -1.

Restricţii

• 1 ≤ N ≤ 5000
• 1 ≤ P ≤ N
• 1 ≤ K ≤ N-1

Exemplu

Cum se trimit solutii?