Kādās milzīgās, pamestās dimantu raktuvēs, vienā no 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ā. 

(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ē.)

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) ( 1 <= T < 2^N) 

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 A_i un B_i, kas apraksta šahtu, kas savieno kambari A_i ar kambari B_i.

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

Apakšuzdevumi

K = 0 (20 punkti)

N ≤ 10 (40 punkti)