Nekādas kafijas!

Lindai ļoti garšo kafija, bet tagad viņa vēlas tās dzeršanu atmest. Pilsētā šobrīd noris kampaņa, kas motivē iedzīvotājus dzert mazāk kafijas, tāpēc atsevišķos kvartālos ir izvietoti reklāmas plakāti, kas mudina atturēties no kafijas lietošanas. Pilsētu veido $N$ kvartāli, kurus savieno $M$ ceļi. Starp katriem diviem kvartāliem var būt ne vairāk kā viens ceļš. No katra kvartāla var nokļūt katrā citā vienā vai vairākos veidos.

Linda katru rītu dodas no mājām uz darbu. Viņa ir ļoti nogurusi, tāpēc, ja pa ceļam kādā kvartālā ir kafijas automāts, Linda gribēs no tā paņemt kafiju. Vienīgais, kas var Lindai palīdzēt atturēties, ir iepriekš minētās kampaņas reklāma, jo tad Lindai palielinās ticība sevī. Reklāmu plakātu izmēri ir dažādi, un katrai reklāmai ir savs ietekmes attālums. Ja ietekmes attālums ir $1$, tad reklāma redzama tikai kvartālā, kurā tā ir izvietota, bet, ja ietekmes attālums ir $2$, tad arī blakus kvartālos (kvartālos, uz kuriem var nokļūt, izmantojot vienu ceļu), un tā tālāk.

Attēlā redzama pilsētas kartes ilustrācija.

Lindas māja (apzīmēta ar $H$) atrodas $4$. kvartālā, bet darbs (apzīmēts ar $D$) - $6$. kvartālā. Kafijas automāti (apzīmēti ar $K_1,K_2,K_3$) atrodas kvartālos $1, 5, 8$ (tie ir apvilkti ar biezāku līniju). Reklāmas $R_1$ un $R_2$ atrodas attiecīgi $2$. un $8$. kvartālā. $R_1$ ietekmes attālums ir $2$, bet $R_2$ ietekmes attālums ir $1$. Reklāmu ietekmētie kvartāli ir iekrāsoti sarkanā krāsā. Ja Linda atradīsies $5$. kvartālā, tad viņa padzersies kafiju, jo šis kvartāls nav reklāmas ietekmes zonā.

Konkrētajā gadījumā Lindai ir divi maršruti, kā nokļūt no mājām uz darbu, nedzerot kafiju:

• 1. maršruts (garums 4): $4 \to 1 \to 2 \to 3 \to 6$
• 2. maršruts (garums 5): $4 \to 7 \to 8 \to 9 \to 10 \to 6$

Uzraksti datorprogrammu, kas palīdzēs Lindai atrast īsākā maršruta no mājām uz darbu, kurā viņa nepadzersies kafiju, garumu! Ja no kafijas dzeršanas izvairīties nevar, jāizvada $-1$.

Pirmajā rindā doti četri naturāli skaitļi - kvartālu skaits $N$ ($N \leq 10^5$), ceļu skaits $M$ ($M \leq 10^5$), mājas kvartāla numurs $H$ ($1 \leq H \leq N$) un darba kvartāla numurs $D$ ($1 \leq D \leq N, H \neq D$).

Nākamajās $M$ rindās katrā doti divi naturāli skaitļi $u_i$ un $v_i$ ($1 \leq u_i, v_i \leq N$, $u_i \neq v_i$) - savienojums starp kvartāliem $u_i$ un $v_i$.

Nākamajā rindā dots vesels nenegatīvs skaitlis - reklāmu skaits $R$ ($R \leq N$). Nākamajās $R$ rindās doti divi naturāli skaitļi $r_i$ un $d_i$ ($1 \leq r_i \leq N$, $1 \leq d_i \leq N$, visiem $i \neq j$ ir spēkā $r_i \neq r_j$) - kvartāls, kur izvietota reklāma, un reklāmas ietekmes attālums.

Nākamajā rindā dots vesels nenegatīvs skaitlis - kafijas automātu skaits $K$ ($K \leq N$). Nākamajā rindā doti $K$ naturāli skaitļi $k_i$ ($1 \leq k_i \leq N$, $k_i \neq H$, $k_i \neq D$, visiem $i \neq j$ ir spēkā $k_i \neq k_j$) - kvartāli, kuros atrodas kafijas automāti.

Vienīgajā rindā jāizvada vesels skaitlis - īsākā ceļa garums no mājām uz darbu, kurā Linda nedzer kafiju. Ja šāds ceļš neeksistē, jāizvada $-1$.