题解传送门

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define N 10010
int n,m,ans;
vector<int>G[N];
int vis[N],match[N];
mt19937 rng;
int dfs(int x){
	shuffle(G[x].begin(),G[x].end(),rng);
	vis[x]=1;
	for(int y:G[x]){
		if(!match[y]){
			vis[y]=1;
			match[y]=x;match[x]=y;
			return 1;
		}
	}
	for(int y:G[x]){
		int z=match[y];
		if(vis[z])continue;
		match[x]=y;match[y]=x;match[z]=0;
		if(dfs(z))return 1;
		match[y]=z;match[z]=y;match[x]=0;
	}
	return 0;
}
signed main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	random_device seed;
	rng=mt19937(seed());
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int x,y;cin>>x>>y;x++,y++;
		G[x].push_back(y);G[y].push_back(x);
	}
	
	for(int i=1;i<=n;i++)if(!match[i]){
		memset(vis,0,sizeof(vis));
		ans+=dfs(i);
	}
	
	cout<<ans<<'\n';
	memset(vis,0,sizeof(vis));
	for(int i=1;i<=n;i++)if(!vis[i]&&match[i]){
		cout<<i-1<<' '<<match[i]-1<<'\n';
		vis[i]=1;vis[match[i]]=1;
	}
	
	return 0;
}