#include<fstream>
#include<vector>
#include<string.h>
#include<algorithm>
#define dim 280
using namespace std;

ifstream f("strazi.in");
ofstream g("strazi.out");
vector< int >G[dim];
int uz[dim],l[dim],r[dim],n,m,i,cnt,change,Drum[dim],EndDrum,x,k,y;
void citire() { 
	
	f>>n>>m;
	
	for(i=1;i<=n;i++){
		f>>x>>y;
		G[x].push_back(y);
	}
	
}
int pairup(int x) {
	
	if(uz[x])
		return 0;
	uz[x]=1;
	int nod;
	for(int i=0;i<G[x].size();++i){
		nod=G[x][i];
		if(!r[nod] ){
			r[nod]=x;
			l[x]=nod;
			return 1;
		}
	}
	for(int i=0;i<G[x].size();++i){
		nod=G[x][i];
		if( r[nod]&& pairup(r[nod]) ){
			r[nod]=x;
			l[x]=nod;
			return 1;
		}
	}
	return 0;
}
void cuplaj () {
	
	change = 1 ;
	
	do{
		
		memset(uz,0,sizeof(uz));
		change = 0;
		
		for(i=1;i<=n;i++)
			if(!l[i])
				change|=pairup(i);
	}while(change);
	
	for(i=1;i<=n;i++)
		if(!l[i])
			++cnt;
	g<<--cnt<<"\n";
	
}
void drum_hamiltonian() {
	
	for(i=1;i<=n;i++){
		
		if(!r[i]){
			
			if(EndDrum)
				g<<EndDrum<<" "<<i<<"\n";
			
			Drum[++k]=i;
			
			for(EndDrum=i;l[EndDrum];EndDrum=l[EndDrum])
				Drum[++k]=l[EndDrum];
			
		}
		
		
	}
	
	for(i=1;i<=k;i++)
		g<<Drum[i]<<" ";
}
int main () {
	
	citire ();
	cuplaj ();
	drum_hamiltonian();
	
	return 0;
}