#include <cstdio>
#include <ctime>
#include <cstdlib>
#include <string>
#include <vector>
#define N 100001

using namespace std;
struct nod
{
    int x; 
    nod *n;
};


nod *a[N];
int n, m;
int l[N], r[N];
bool use[N];

vector<int> sol[N];

inline void add(int i, int j)
{
    nod *p=new nod;
    p->x=j;
    p->n=a[i];
    a[i]=p;
}

void read()
{
    freopen("strazi.in","r",stdin);

    scanf("%d %d\n", &n, &m);
    
    int p, q;

    while(m--)
    {
	scanf("%d %d\n", &p, &q);

	add(p,q);
    }

}

inline bool pairup(int n)
{
    if(use[n]) return 0;
    use[n]=1;

    nod *i;

    for(i=a[n]; i; i=i->n)
	if(!l[i->x])
	{
	    l[i->x]=n;
	    r[n]=i->x;
	    return 1;
	}


    for(i=a[n]; i; i=i->n)
	if(pairup(l[i->x]))
	{
	    l[i->x]=n;
	    r[n]=i->x;
	    return 1;
	}

    return 0;
}

void solve()
// Hopcroft-Karp
{
    int flow=0, i, ok=1;

    while(ok)
    {
	ok=0;

	for(i=1; i <= n; ++i) use[i]=0;

	for(i=1; i <= n; ++i)
	    if(!r[i])
		if(pairup(i)) ++flow, ok=1;
    }

}

int sorted[N], ns;


void dfs(int n)
{
    if(!n) return ;
    if(use[n]) return;

    use[n]=1;
    dfs(r[n]);

    sorted[++ns]=n;
}

int nr;

void DF(int n)
{
	if(!n) return ;
	if(use[n]) return;
	
	use[n]=1;
	sol[nr].push_back(n);
	
	DF(r[n]);
	
}
void df(int n)
{
    if(!n) return;
    if(use[n]) return;

    use[n]=1; 
    //sol[nr].push_back(n);
	printf("%d ", n);
    df(r[n]);

}

int main()
{
	freopen("strazi.out","w",stdout);
    read();
    solve();

    int i;
    
    for(i=1; i <= n; ++i) use[i]=0;


    for(i=1 ;i <= n; ++i)
	if(!use[i]) 
	    dfs(i);
	
	nr=0;
	
    for(i=1; i <= n; ++i) use[i]=0;
	for(i=n; i ; --i)
		if(!use[sorted[i]])
		{
			++nr;
			DF(sorted[i]);
		}
			
  printf("%d\n", nr-1);    
    for(i=1; i < nr; ++i)
	printf("%d %d\n", sol[i][sol[i].size()-1], sol[i+1][0]);

	
    for(i=1; i <= n; ++i) use[i]=0;

    for(i=n; i; --i)
	if(!use[sorted[i]])
	{
	    ++nr;
	    df(sorted[i]);
	}

	printf("\n");
/*
	for(i=1; i <= nr; ++i)
	{
		for(int j=0; j < sol[i].size(); ++j) printf("%d ", sol[i][j]);
		printf("\n");
	}
	printf("\n");
  
*/
	// freopen("strazi.out","w",stdout);
  
  //  printf("%d %d\n", sol[nr][sol[nr].size()-1], sol[1][0]);

    return 0;
}