Disegna senza sollevare la matita

Consideriamo il classico problema di disegnare una casetta (con una X nel suo riquadro centrale) senza sollevare mai la punta della matita.

In generale, sono dati N vertici, numerati da 1 a N, e M lati che li collegano.
Dati due vertici A e B, dovete indicare la sequenza di lati (vanno presi tutti!) da attraversare in modo da collegare A a B passando attraverso tutti i lati nell’ordine indicato dalla sequenza (senza alzare quindi la matita).
Ciascun lato deve essere percorso una sola volta, in una delle due direzioni a scelta.

Dati in Input

Il file input.txt è composto da M+1 righe.

• La prima riga contiene quattro interi N, M, A e B separati da uno spazio: il numero di vertici, il numero di lati che li collegano, il vertice di partenza e quello di arrivo.
• Le successive M righe contengono i lati, un lato per riga che viene rappresentato da una coppia di interi separati da uno spazio (dove i due interi sono i numeri dei vertici collegati da tale lato).

Dati in Output

Il file output.txt è composto da M righe, che riportano la sequenza ordinata dei lati da disegnare per andare da A a B, passando come già detto attraverso tutti i lati una e una sola volta.
Se un lato collega due vertici X e Y, deve essere stampato (indipendentemente da come è letto nell’input) come la coppia di interi X eY separati da uno spazio se il lato viene viene percorso da X a Y, e come la coppia di interi Y e X separati da uno spazio se il lato viene viene percorso da Y a X (vedi esempio).

Assunzioni

• 1 <= N <= 100000
• 1 <= M <= 1000000
• 1 <= A, B <= N e A<>B

Esempi

Nota

1. Viene garantito che sia sempre possibile disegnare senza alzare la matita.
   Nel caso vi siano più soluzioni valide, è sufficiente restituirne una.
2. Non esistono lati multipli che collegano la stessa coppia di vertici.
   Tutti i vertici e tutti gli archi devono essere attraversati dalla matita.
3. Per chi non lo avesse riconosciuto, questo è il noto problema del matematico Eulero.