Un garaj subteran are N locuri de parcare, plasate pe diferite niveluri. Locurile
de parcare sunt numerotate distinct de la 1 la N. Locul de parcare numarul 1
este intrarea/iesirea din garaj, se afla la nivelul cel mai inalt al garajului
si aici nu este parcata nici o masina.
Un loc de parcare este practic o camera in care incape o singura masina si care
poate comunica prin coridoare cu alte locuri de parcare, astfel incat exista
un singur drum de la un loc de parcare la altul. Un drum de la un loc de parcare
catre iesire consta dintr-o succesiune de camere, astfel incat intre oricare
doua camere consecutive exista coridor de trecere, iar camerele sunt plasate
pe niveluri consecutive in garaj. Evident, o masina nu poate trece printr-o
camera daca in acea camera este parcata o alta masina.
Ion si-a parcat masina in locul de parcare numarul P si acum ar vrea sa plece.
Problema este ca exista si alte masini parcate in drumul sau catre iesire. Pentru
a-si elibera drumul va trebui sa mute fiecare masina care il incurca intr-un
alt loc de parcare, plasat la un nivel inferior celui in care se afla masina
respectiva.
O mutare consta in impingerea unei masini intr-o camera de pe nivelul imediat
inferior.
Cerinta
Scrieti un program care sa determine numarul minim de mutari pe care trebuie
sa le faca Ion pentru a putea parasi garajul.
Date de intrare
Fisierul de intrare garaj.in
contine pe prima linie 3 numere naturale N P K separate prin spatii reprezentand
numarul de locuri de parcare, locul in care este parcata masina lui Ion, precum
si numarul de locuri de parcare ocupate de alte masini (altele decat masina
lui Ion). Fiecare dintre urmatoarele N linii contine informatii despre locurile de parcare.
Mai exact pe linia (i+1) se afla numerele celor T locuri de parcare conectate
prin coridoare de locul de parcare i, situate pe nivelul imediat inferior nivelului
pe care se afla locul i, sub forma: T A1 A2 ... AT
Ultima linie a fisierului de intrare contine K numere naturale, separate prin
spatii, reprezentand numerele locurilor de parcare ocupate de cele K masini
existente in garaj.
Date de iesire
Fisierul de iesire garaj.out
contine o singura linie pe care se afla numarul minim de mutari pe care trebuie
sa le faca Ion pentru a putea iesi cu masina din garaj. Daca nu exista solutie,
pe prima linie a fisierului de iesire se va scrie mesajul IMPOSIBIL
Restrictii
Ion nu va muta masina sa pana cand drumul catre iesire nu este complet eliberat.
2 <= N <= 5000
2 <= P <= N
0 <= K <= N-2
Exemple
garaj.in
garaj.out
8 5 3
1 3
1 7
2 2 4
2 5 6
0
0
1 8
0
2 3 7
2
garaj.in
garaj.out
6 4 2
2 5 6
0
0
0
2 4 2
1 3
6 5
1
garaj.in
garaj.out
6 3 2
1 4
1 6
0
1 5
2 2 3
0
4 5
4
prof. Emanuela Cerchez
Liceul de Informatica "Grigore Moisil" Iasi