trip

Gigel s-a hotarat sa face o calatorie prin tara sa. El vrea sa mearga pana intr-un oras destinatie iar apoi sa se intoarca in orasul din care a plecat. Pentru ca excursia sa nu devina prea monotona, Gigel a pus urmatoarea conditie: drumul de la dus si cel de la intoarcere trebuie sa contina un numar minim de sosele comune. (Nici drumul de la dus, nici cel de la intoarcere nu au voie sa parcurga aceeasi sosea de la multe ori).

Cerinta

Scrieti un program care sa-l ajute pe Gigel sa gaseasca un drum dus-intors care sa contina cat mai putine sosele comune.

Date de intrare

Pe prima linie a fisierul trip.in se afla 2 intregi S si D (S<>D) care reprezinta orasul de plecare si orasul destinatie. Urmatoarea linie contine 2 intregi N si M, unde N (3<=N<=1000) este numarul de orase si M (2<=M<=100000) este numarul de sosele. Urmatoarele M linii contin cate 2 intregi P si Q (1<=P<=N, 1<=Q<=N, P<>Q) cu semnificatia ca intre orasul P si orasul Q exista o sosea (pe care se poate merge in ambele sensuri). Orasele sunt numerotate de la 1 la N.

Date de iesire

Prima linie a fisierului trip.out trebuie sa contina un intreg care reprezinta numarul minum de sosele comune pe care le au cele doua drumuri. A doua linie trebuie sa contina o succesiune de noduri care reprezinta drumul de la S la D (succesiunea trebuie sa contina si S si D). A treia linie trebuie sa contina un drum de intoarcere de la D la S. Daca nu exista doua astfel de drumuri, fisierul de iesire va contine -1.

Restrictii

• N<=1000 (o mie)
• M<=100000 (o sute de mii)
• Nodurile sunt numerotate de la 1 la N
• Soselele sunt bidirectionale
• Cele doua drumuri descrise in fisierul de iesire trebuie sa includa orasul de plecare si cel de sosire
• Daca exista mai multe perechi de drumuri care satisfac conditia impusa de Gigel, in fisierul de iesire se va scrie o singura pereche
• Daca nu exista doua astfel de drumuri, fisierul de iesire va contine numai -1
• Se acorda punctaje partiale (vezi modul de punctare de mai jos)

   

Exemple

trip.in	trip.out
1 6 7 8 2 1 1 3 2 3 4 2 4 5 5 6 7 5 6 7	2 1 3 2 4 5 7 6 6 5 4 2 1

Mod de punctare

Daca prima linie contine numarul corect de sosele comune, obtineti 2 puncte. Daca drumurile de pe liniile 2 si 3 sunt corecte, mai obtineti inca 3 puncte (deci 5 puncte in total). Daca prima linie este gresita nu primiti nici un punct (chiar daca cele doua drumuri sunt corecte).