#include <stdio.h>
#include <vector>
#define NMax 260
int n, m, uz[NMax], path[NMax], mat[NMax][NMax];
std::vector<int> a[NMax], fin;
void citire();
void rez();
void bfs( int x );
void redo( int x, int type );
void redo2( int x, int type );
void afis( int x, FILE *g );
int main()
{
citire();
rez();
return 0;
}
void afis( int x, FILE *g )
{
if ( path[x] == -1 )
{
fprintf( g, "%d ", x );
return;
}
afis( path[x], g );
fprintf( g, "%d ", x );
}
void redo2( int x, int type )
{
if ( path[x] == -1 )
return;
uz[x] = type;
redo( path[x], type-1 );
}
void redo( int x, int type )
{
if ( path[x] == -1 )
return;
uz[x] = type;
redo( path[x], type );
}
void bfs( int x )
{
int i, in, sf, max, nrmax, first, ok, okbig = 0, C[NMax];
std::vector<int> lista;
in = sf = 0;
C[0] = x;
path[x] = -1;
uz[x] = 1;
nrmax = x;
while( in <= sf )
{
first = C[in++];
max = a[first].size();
// vad vecinii unui nod
for (i=0,ok=0; i<max; i++)
{
if ( !uz[a[first].at(i)] )
{
ok = okbig = 1;
C[++sf] = a[first].at(i);
uz[C[sf]] = 1 + uz[first];
path[C[sf]] = first;
}
}
// daca nu ma mai pot duce nicaieri
if ( !ok )
{
// il adaug in lista
lista.push_back( first );
// vad daca am un vf mai bun ca lungime
if ( uz[nrmax] < uz[first] )
nrmax = first;
}
}
max = lista.size();
for (i=0; i<max; i++)
if ( lista.at(i) != nrmax )
redo( lista.at(i), 0 );
redo2( nrmax, uz[nrmax] );
if ( !okbig )
{
okbig = 1;
for (i=1; i<=n && okbig; i++)
{
if ( mat[i][x] && !uz[i] )
okbig = 0;
}
if ( okbig )
fin.push_back( x );
}
else
{
fin.push_back( nrmax );
}
}
void rez()
{
int i, max;
FILE *g = fopen( "strazi.out", "wt" );
for (i=1; i<=n; i++)
if ( !uz[i] )
{
bfs( i );
}
max = fin.size();
fprintf( g, "%d\n", max-1 );
for (i=0; i<max-1; i++)
{
fprintf( g, "%d %d\n", fin[i], fin[i+1] );
path[fin[i+1]] = fin[i];
}
afis( fin[i], g );
}
void citire()
{
int i, x, y;
FILE *f = fopen( "strazi.in", "rt" );
fscanf( f, "%d %d", &n, &m );
for (i=0; i<m; i++)
{
fscanf( f, "%d %d", &x, &y );
a[x].push_back( y );
mat[x][y] = 1;
}
fclose( f );
}