Nosaukums
Binārās Raktuves (binary_mine)
Laika limits
0.10s
Atmiņas limits
256.0 MB
Grūtība
21%

Definīcija

Kādās milzīgās, pamestās dimantu raktuvēs, vienā no dziļākajiem kambariem ir paslēpta dārgumu lāde. Raktuves sastāv no vairākiem kambariem, kas dziļumā izvietoti N līmeņos. Katrā līmenī i ir tieši 2(i-1) kambaru. Katrs kambaris, izmantojot kāpnes, ir savienots tieši ar 1 augstāk esošu kambari (izņemot visaugstāk esošo kambari, kurš tā vietā ir savienots ar virszemi). Kambaris ar kāpņu palīdzību nevar būt savienots ar vairāk kā 2 zemāk esošiem kambariem. Papildu kāpnēm, raktuvēs ir izbūvētas arī šahtas, kas var savienot jebkurus divus kambarus. Kambari ir numurēti secīgi tā, kā tas ir parādīts ilustrācijā. 

 

 Raktuvju ilustrācija

(raktuves ilustrācija: ar sarkanu atzīmētas satrūdējušās kāpnes, ar raustītām bultām - šahtas, ar dzeltenu - kambaris ar dārgumiem)

 

 K skaits kāpņu ir satrūdējušas, tādēļ tās nav izmantojamas. Jūsu uzdevums ir noskaidrot, kāds ir minimālais kambaru skaits, kuri ir jāapmeklē, lai no virszemes tiktu līdz dārgumiem. (Tiek garantēts, ka šāds ceļš eksistē.)


Ievaddatu raksturojums

Pirmajā rindā doti četri veseli skaitļi N (līmeņu skaits), K (salūzušo kāpņu skaits), M (šahtu skaits) T (kambara numurs, kurā atrodas dārgumi) ( 0 <= N <= 60) (0 <= K, M <= 100) ( 2(N-1) <= T < 2N

Nākamajās K rindās seko  kambaru numuri, kuriem augšupejošās kāpnes ir satrūdējušas.

Pēc tam seko M rindas, kur katrā rindā doti 2 veseli skaitļi Ai un Bi, kas apraksta šahtu, kas savieno kambari Ai ar kambari Bi.

 


Izvaddatu raksturojums

Izvadiet vienu veselu skaitli - mazāko iespējamo kambaru skaitu kāds jāapmeklē, lai no virszemes tiktu līdz dārgumiem.


Piezīmes

Apakšuzdevumi

K = 0 (20 punkti)

 10 (40 punkti)


Paraugdati

Stdin
3 2 2 5
5
3
7 4
3 5
Stdout
6

Stdin
3 0 1 5
1 5
Stdout
2

Uzdevums tiek aizsargāts ar autortiesībām un tā kopēšana vai neatļauta izmantošana ir aizliegta.