/*      

Condominio (selezioni nazionali 2002)

Copyright (C) 2002 Sebastiano Vigna 

This program is free software; you can redistribute it and/or modify it
under the terms of the GNU General Public License as published by the
Free Software Foundation; either version 2, or (at your option) any
later version.
	
This program is distributed in the hope that it will be useful, but
WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
General Public License for more details.
	
You should have received a copy of the GNU General Public License along
with this program; see the file COPYING.  If not, write to the Free
Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
02111-1307, USA.  


Questa soluzione (che non era previsto venisse trovata) è l'unica in grado di
enumerare tutti i cicli nei vincoli di tempo. È un algoritmo CAT (tempo
ammortizzato costante) pubblicato in D. B. Johnson, Finding all the elementary
circuits of a directed graph SIAM J. Comput., 4(1), pp. 77-84, March 1975.

*/

#include <stdio.h>
#include <string.h>

#define MAXN 1000

/* Numero di nodi e archi complessivi del grafo. */
int N, M;

char G[MAXN][MAXN]; /* Matrice di adiacenza. */
char b[MAXN];       /* I nodi bloccati. */

int B[MAXN][MAXN]; /* Per ogni nodo v, la lista di nodi che vanno sbloccati
							 quando v viene sbloccato. */
int lB[MAXN];		 /* La lunghezza di ciascuna lista. */
int blocca[MAXN][MAXN]; /* Matrice di comodo: B[u][i] = v per qualche i<lB[u] sse blocca[u][v]. */


int A[MAXN];		/* Lista dei nodi della componente connessa corrente */
int n;				/* Dimensione della componente connessa corrente. */
int s;				/* Minimo vertice corrente nella costruzione dei cammini. */

int pila[MAXN], l; /* La pila di nodi corrente. */



#define min( a, b )    ( (a) < (b) ? (a) : (b) )


/* La funzione seguente implementa l'algoritmo di Tarjan per le componenti
connesse forti, con una variante: la componente viene costruita utilizzando
solo nodi di indice superiore a s. Inoltre, una volta costruita la componente
contenente s la visita viene interrotta. */

int rad[MAXN]; /* Numero di radice corrente di un nodo. */
int comp[MAXN]; /* Numero di componente connessa di un nodo */
int vis[MAXN]; /* Nodo visitato. */
int id;			/* Id progressivo assegnato via via ai nodi. */
int ncomp;     /* Numero corrente componente. */

int visita( int v ) {
	int w;
	int i, t, f;

	vis[v] = 1;
	comp[v] = 0;
	rad[v] = t = ++id; 
	pila[l++] = v;
	
	for ( w = s; w < N; w++ ) 
		if (G[v][w]) {
			if (G[v][w] && !vis[w]) {
				if (!visita( w )) return 0;
			}
			if ( !comp[w] ) rad[ v ] = min( rad[ v ], rad[ w ] );
		}
	
	if ( rad[ v ] == t ) {
		f = 0;
		n = 0;
		++ncomp;
		do {
			/* Accumuliamo la componente corrent in A, e controlliamo
				se dentro c'è s. In tal caso, poniamo f a 1 in modo da
				interrompere la visita. */
			A[n++] = w = pila[--l];
			comp[w] = ncomp;
			if (w == s) f = 1;
		} while ( w != v );
		
		return !f;
	}
	
	return 1;
}



/* L'algoritmo di Johnson per i cicli elementari. */

int tot; /* Numero totale di cicli. */


void sblocca(int u) {
	int i;
	
	b[u] = 0;
	
	while(lB[u] > 0) {
		lB[u]--;
		blocca[u][B[u][lB[u]]] = 0;
		if (b[B[u][lB[u]]]) sblocca(B[u][lB[u]]);
	}
}

int circuito(int v) {
	int i, j, w, f=0;
	
	pila[l++] = v; /* v sulla pila */
	b[v] = 1;
	for(i=0; i<n; i++)
		if (G[v][A[i]]) {
			
			if (A[i] == s) {
				for(j=0; j<l; j++) printf("%s%d", j ? " " : "", pila[j]+1);
				printf("\n");
				f = 1;
				tot++;
			}
			else if (!b[A[i]] && circuito(A[i])) f = 1;
		}
	
	if (f) sblocca(v);
	else 
		for(i=0; i<n; i++) 
			if (G[v][A[i]] && !blocca[A[i]][v]) {
				B[A[i]][lB[A[i]]++] = v;
				blocca[A[i]][v] = 1;
			}
	
	l--; /* v via dalla pila */
	return f;	
}

int main() {
	FILE *f;
	int i, j, k;
	
	f=stdin;
	fscanf(f,"%d",&N);
	fscanf(f,"%d",&M);
	for (i=0; i<M; i++) {
		fscanf(f,"%d %d",&j,&k);
		G[j-1][k-1]=1;
	}
	
	/* s è il vertice minimo considerato. */
	for(s=0; s<N; s++) {
		id = ncomp = 0;
		for(i=s; i<N; i++) vis[i] = 0;

		/* Calcoliamo la componente connessa contenente s e avente
			tutti i nodi di indice superiore a s. */
		visita(s);

		if (n > 1) {

			/* Azzera le informazioni di blocco per i vertici nella componente. */
			for(i=0; i<n; i++) {
				b[A[i]] = 0;
				lB[A[i]] = 0;
				for(j=0; j<n; j++) blocca[A[i]][A[j]] = 0;
			}

			circuito(s);
		}
	}

	//fprintf(stderr, "TOTALE: %d\n", tot);
}