garaza Pazemes garāža 1 sek.  Uzdevums Pazemes garāža sastāv no N stāvvietām, kas izvietotas dažādos stāvos. Visas stāvvietas ir sanumurētas ar naturāliem skaitļiem no 1 līdz N pēc kārtas. Katra stāvvieta ir neliela izolēta telpa, kurā var novietot ne vairāk kā vienu automašīnu. Dažas no telpām ir savienotas savā starpā ar pasāžu palīdzību. Automašīna nevar izbraukt cauri aizņemtai telpai. Izeja no garāžas atrodas telpā Nr.1, kurā nedrīkst novietot nevienu automašīnu (bet jebkura mašīna šai telpai var braukt cauri). Starp jebkurām divām telpām eksistē viens vienīgs maršruts. Katras divas pēc kārtas esošas telpas šādā maršrutā atrodas garāžas blakus stāvos, pie kam telpa, kas atrodas tuvāk izejai, vienmēr atrodas augstākā stāvā. Ralfs savu automašīnu ir novietojis telpā, kuras numurs ir P un tagad viņš vēlētos izbraukt no garāžas. Diemžēl dažas no mašīnām atrodas telpās caur kurām Ralfam jābrauc. Vienīgā iespēja ir visas ceļā stāvošās mašīnas pārvietot uz zemāku stāvu. Par vienu pārvietošanu sauksim vienas automašīnas pārvietošanu uz brīvu telpu vienu stāvu zemāk. Uzrakstiet programmu, kas nosaka, kāds mazākais pārvietošanu skaits jāveic, lai Ralfs varētu nokļūt līdz garāžas izejai (istabai ar numuru 1)! Ralfs nedrīkst pārvietot savu automašīnu pirms ceļš nav pilnībā atbrīvots.    Ievaddati Teksta faila garaza.dat pirmajā rindā dotas trīs veselu skaitļu N(telpu skaits, 2 ≤N≤5000), P(telpas, kurā atrodas Ralfa automašīna, numurs, 2≤P≤N) un K (automašīnu skaits garāžā, neskaitot Ralfa automašīnu, 0≤K≤N-2) vērtības, kas atdalītas ar tukšumsimboliem. Katra no nākošajām N faila rindām satur informāciju par vienu telpu. i+1-ajā faila rindā ir dati par telpām, kas ir tieši savienotas ar i-to telpu un atrodas zemāk par to formā: T A1 A2 ... AT ,kur T ir šādu telpu skaits, bet A1, A2, ..., AT - šo telpu numuri. Faila pēdējā rindā ir doti K naturāli skaitļi - aizņemto telpu numuri (neskaitot Ralfa automašīnas aizņemto telpu).    Izvaddati Teksta faila garaza.rez vienīgajā rindā jāizvada mazākais pārvietošanu skaits, kāds Ralfam jāveic, lai atbrīvotu ceļu līdz izejai. Ja ceļu atbrīvot nav iespējams, failā jāizvada tikai vārds 'NEVAR'.    Piemērs garaza.dat garaza.rez 6 3 2 1 4 1 6 0 1 5 2 2 3 0 4 5 4     garaza.dat garaza.rez 6 4 2 2 5 6 0 0 0 2 4 2 1 3 6 5 1     garaza.dat garaza.rez 8 5 3 1 3 1 7 2 2 4 2 5 6 0 0 1 8 0 2 3 7 2    Atsauces Uzdevums izmantots Horvātijas informātikas olimpiādē 2002.gadā Drukāšanai