Condominio

Le tubature di un condominio sono state rimaneggiate così tante volte che nessuno si ricorda più bene come l’acqua dovrebbe essere distribuita.
Gli operai hanno creato molti raccordi temporanei, che non sono stati più rimossi, creando una vera ragnatela di tubi e giunture.

Quando però una serie di tubi sono collegati fino a formare un anello in cui l’acqua scorre circolarmente la situazione è particolarmente grave, perché l’acqua può cominciare ad andare in circolo, creando sbalzi di pressione e scoppi delle tubature.

Il vostro compito è aiutare l’amministratore del condominio a risolvere questo problema.
Per fare ciò, dovete aiutarlo a trovare tutti gli anelli, cioè tutte le sequenze di tubi che partono e terminano nello stesso giunto (senza passare mai due volte per lo stesso giunto), e in cui l’acqua scorre sempre nello stesso verso.

Per esempio, nella rete di tubi e giunti rappresentata in figura 1,

Figura 1
Un esempio di rete condominiale.

Dati in input

Il file di input, di nome input.txt, contiene sulla prima riga due interi G e T, che sono il numero di giunti e di tubi. Ogni tubo collega un giunto a un altro giunto. Su ciascuna delle successive T righe compaiono due interi, che sono il giunto di partenza e quello di arrivo di un tubo. Più precisamente, nella riga i del file compaiono il giunto iniziale e quello finale del tubo (i-1)-esimo (sia i giunti che i tubi sono numerati a partire da uno). L’acqua scorre dal giunto di partenza a quello di arrivo.

Dati in output

Il file di output, di nome output.txt, contiene una lista di anelli presenti nella rete condominiale. Ogni anello viene descritto tramite la sequenza dei giunti che attraversa, separati da uno spazio.

Assunzioni

1. il tempo limite di esecuzione è fissato in 5 secondi;
2. 1 <= G <= 200;
3. non ci sono mai più di 100000 anelli nella rete condominiale;

Esempio

L’esempio è quello mostrato in Figura 1.