#line 1 "verify/yosupo/graph/general_matching.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/general_matching"
#line 2 "template.hpp"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define ALL(a) a.begin(),a.end()
#define RALL(a) a.rbegin(),a.rend()
#define SORT(a) sort(ALL(a))
#define RSORT(a) sort(RALL(a))
#define REV(a) reverse(ALL(a))
#define UNI(a) a.erase(unique(ALL(a)),a.end())
#define SZ(a) (int)(a.size())
#define LB(a,x) (int)(lower_bound(ALL(a),x)-a.begin())
#define UB(a,x) (int)(upper_bound(ALL(a),x)-a.begin())
#define MIN(a) *min_element(ALL(a))
#define MAX(a) *max_element(ALL(a))
using ll = long long;
using db = long double;
using i128 = __int128_t;
using u32 = uint32_t;
using u64 = uint64_t;
const int INF=INT_MAX/2;
const ll LINF=LLONG_MAX/4;
const db DINF=numeric_limits<db>::infinity();
const int MOD=998244353;
const int MOD2=1000000007;
const db EPS=1e-9;
const db PI=acos(db(-1));
template<class T>
using PQ = priority_queue<T,vector<T>,greater<T>>;
#define vv(T,a,n,...) vector<vector<T>> a(n,vector<T>(__VA_ARGS__))
#define vvv(T,a,n,m,...) vector<vector<vector<T>>> a(n,vector<vector<T>>(m,vector<T>(__VA_ARGS__)))
#define vvvv(T,a,n,m,k,...) vector<vector<vector<vector<T>>>> a(n,vector<vector<vector<T>>>(m,vector<vector<T>>(k,vector<T>(__VA_ARGS__))))
template<class T,class U>
bool chmin(T &a,U b){return b<a?a=b,1:0;}
template<class T,class U>
bool chmax(T &a,U b){return a<b?a=b,1:0;}
template<class T,class U>
T SUM(const U &a){return accumulate(ALL(a),T{});}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rng64(chrono::steady_clock::now().time_since_epoch().count());
#line 2 "flow/general-matching.hpp"
/**
* Author: Teetat T.
* Date: 2025-09-03
* Description: General matching using blossom algorithm.
* Time: O(E V \alpha(V)).
*/
template<int N>
struct GeneralMatching{
int n,m;
vector<int> adj[N+1];
int fa[N+1],link[N+1],match[N+1],vis[N+1],dep[N+1];
queue<int> q;
int find(int u){
while(fa[u]!=u)u=fa[u]=fa[fa[u]];
return u;
}
int get_lca(int u,int v){
u=find(u),v=find(v);
while(u!=v){
if(dep[u]<dep[v])swap(u,v);
u=find(link[match[u]]);
}
return u;
}
void blossom(int u,int v,int lca){
while(find(u)!=lca){
link[u]=v;
v=match[u];
if(vis[v]==0){
vis[v]=1;
q.emplace(v);
}
fa[u]=fa[v]=lca;
u=link[v];
}
}
bool augment(int st){
for(int i=1;i<=n;i++)fa[i]=i;
for(int i=1;i<=n;i++)vis[i]=-1;
vis[st]=1;
dep[st]=0;
q=queue<int>();
q.emplace(st);
while(!q.empty()){
int u=q.front();
q.pop();
for(auto v:adj[u]){
if(vis[v]==-1){
vis[v]=0;
link[v]=u;
dep[v]=dep[u]+1;
if(!match[v]){
for(int x=v,y=u,z;y;y=link[x=z]){
z=match[y];
match[x]=y;
match[y]=x;
}
return 1;
}
vis[match[v]]=1;
dep[match[v]]=dep[u]+2;
q.emplace(match[v]);
}else if(vis[v]==1&&find(u)!=find(v)){
int lca=get_lca(u,v);
blossom(u,v,lca);
blossom(v,u,lca);
}
}
}
return 0;
}
int solve(){
int ans=0;
for(int u=1;u<=n;u++)if(!match[u]){
for(auto v:adj[u])if(!match[v]){
match[u]=v;
match[v]=u;
ans++;
break;
}
}
for(int u=1;u<=n;u++)if(!match[u])ans+=augment(u);
return ans;
}
void init(int _n){
n=_n;
for(int i=1;i<=n;i++)match[i]=0;
for(int i=1;i<=n;i++)adj[i].clear();
}
void add_edge(int u,int v){
adj[u].emplace_back(v);
adj[v].emplace_back(u);
}
};
#line 4 "verify/yosupo/graph/general_matching.test.cpp"
GeneralMatching<500> gm;
int main(){
cin.tie(nullptr)->sync_with_stdio(false);
int n,m;
cin >> n >> m;
gm.init(n);
for(int i=0;i<m;i++){
int u,v,w;
cin >> u >> v;
u++,v++;
gm.add_edge(u,v);
}
cout << gm.solve() << "\n";
for(int i=1;i<=n;i++){
if(gm.match[i]>i){
cout << i-1 << " " << gm.match[i]-1 << "\n";
}
}
}
verify/yosupo/graph/general_matching.test.cpp