foresight

Zhuge Liang, cunoscut și după numele Kongming, vrea să readucă dinastia Han la putere. După ce a unificat regiunea Shu Han, el plănuiește o campanie militară împotriva regiunii Cao Wei.

China este constituită din N teritorii numerotate de la 0 la N − 1 și M drumuri bidirecționale. Fiind o țară vastă, durata de călătorie pe orice drum este de o singură zi. Formal, este un multigraf neorientat fără costuri, care poate conține bucle.

Armata este poziționată inițial în regiunea Shu Han, reprezentată de nodul S, și trebuie să ajungă în regiunea Cao Wei, reprezentată de nodul T, călătorind doar pe drumuri. O singură dată în timpul călătoriei, când armata se află într-o regiune (adică nu călătorește pe un drum), armata inamică poate să blocheze exact un drum, fiind imposibilă folosirea acestuia mai departe. Armata va afla imediat care drum a fost blocat și poate să își ajusteze ruta oricum dorește.

Zhuge Liang a prezis această posibilitate și vrea să aleagă o rută de la S la T care minimizează timpul total al călătoriei în cel mai rău scenariu. Scrieți un program care află timpul optim în cel mai rău caz și găsește o rută optimă.

Date de intrare

Pe prima linie se află numerele N, M, S și T cu semnificația din enunț. Pe următoarele M linii sunt descrise muchiile grafului sub forma U V.

Date de intrare

Pe prima linie se vor afișa opt - timpul optim în cel mai rău caz și len - lungimea rutei optime. Pe următoarea linie se va afișa ruta optimă formată din len + 1 regiuni. Dacă nu există nicio soluție se va afișa doar −1.

Restricţii

• 1 ≤ N ≤ 100 000
• 0 ≤ M ≤ 1 000 000
• $0 ≤ S, T, U_i, V_i < N$

Subtask 1 (17 puncte)

• 1 ≤ N ≤ 1 000

Subtask 2 (19 puncte)

• 1 ≤ N ≤ 4 000

Subtask 3 (43 puncte)

• 1 ≤ N ≤ 30 000

Subtask 4 (21 puncte)

• 1 ≤ N ≤ 100 000

Exemple

stdin

7 10 0 6
0 1
0 2
1 1
1 3
2 3
3 4
3 4
4 5
4 6
5 6

stdout

6 4
0 1 3 4 6

stdin

2 1 0 1
0 1

stdout

-1

Explicații

Parcurgând drumul plănuit, atunci când armata se află în nodul 1, armata inamică poate bloca drumul de la 1 la 3. Armata va fi nevoită să meargă în continuare pe drumul format din nodurile 1, 0, 2, 3, 4, 6. Lungimea acestui drum este 6.

În toate variantele posibile în care se scoate o muchie, cel mai rău drum va fi cel mult 6. Dintre toate planurile posibile, drumul în output este cel optim.