Istoria orasului Kimberley incepe odata cu primul diamant descoperit in Africa de Sud, la sud de raul Orange, in 1867.
Primele case construite in acest loc de catre cautatorii de diamante se pastreaza si acum in centrul orasului.
Intre anii 1870-1880, mina din Kimberley producea peste 95% din totalul de diamante din intreaga lume. Aici a fost descoperit faimosul diamant "Steaua Africii".
Dealul in care s-a sapat initial a disparut, in locul lui ramanand o imensa groapa.

Ne intoarcem la 1870, in vremea cand mina era formata dintr-o retea de galerii subterane.
Problema noastra, presupune ca mina Kimberley este formata din G galerii, foarte inguste. Timpul necesar unui miner sa parcurga oricare dintre galerii, este de un minut. In fiecare minut, doar un singur miner poate sa traverseze o galerie, fie intr-un sens, fie in sens opus.
Fronturile de lucru se numesc "sali". Fiecare sala este capatul uneia sau al mai multor galerii si fiecare galerie are la cele doua capete cate o sala. Oricare doua sali comunica intre ele printr-o galerie care le uneste direct, sau prin intermediul altor galerii.
Exista N sali in mina Kimberley, pe care minerii le identifica prin numerele 1, 2, ... N. Presupunem ca o echipa formata din M mineri, au terminat lucrul in schimbul de noapte. Au lucrat cu totii in frontul de lucru din sala cu numarul de ordine S. Ei trebuie sa ajunga in sala cu numarul D, care este pozitionata la iesirea din mina. Exista in permanenta pericolul prabusirii galeriilor. Din acest motiv, echipa de mineri doreste sa iasa din mina in cel mai scurt timp posibil.

Cerinta

Gasiti timpul minim necesar, pentru ca toti minerii din schimbul de noapte sa poata iesi mina.

Date de intrare

Fisierul kimberley.in, are pe prima linie numerele naturale N si G, pe linia a doua trei numere naturale S, D si M, iar pe urmatoare G linii, cate doua numere naturale reprezentand numerele de ordine ale salilor de la capatul fiecareia dintre cele G galerii. Numerele de pe fiecare linie sunt despartite prin cate un singur spatiu.

Date de iesire

Fisierul kimberley.out va contine o singura linie pe care va fi scris numarul T, reprezentand cel mai surt timp posibil in care toti minerii vor ajunge in sala D, la iesirea din mina Kimberley.

Restrictii si precizari

• 1 <= N, S, D <= 50, 1 <= G <= 100, 1 <= M <= 150
• Nici o galerie nu are la capete aceeasi sala.
• Oricare doua sali sunt conectate prin cel mult o galerie.
• Oricare dintre sali, este suficient de incapatoare, incat poate adaposti toti minerii in acelasi moment de timp.
• Singurele persoane din mina se considera a fi cei N mineri din schimbul de noapte.

Exemplu