对每个连通块分别处理 度数是奇数的点必然是偶数个 把度数是奇数的点之间连上边,变成偶数度 然后跑欧拉回路即可
//#pragma GCC optimize("O3")
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<bits/stdc++.h>
using namespace std;
function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};
const int MAXN = 222;
int n,m,belong[MAXN],ID,deg[MAXN],cur[MAXN];
vector<int> G[MAXN],S[MAXN];
vector<pair<int,int> > es[MAXN],ret;
void getMark(int u, int id){
belong[u] = id;
S[id].push_back(u);
for(int v : G[u]){
if(belong[v]) continue;
getMark(v,id);
}
}
struct Graph{
int head[MAXN],to[MAXN*MAXN],nxt[MAXN*MAXN],tot;
bool real[MAXN*MAXN],vis[MAXN*MAXN];
void ADDEDGE(int u, int v, bool r){
to[tot] = v; nxt[tot] = head[u];
vis[tot] = false;
real[tot] = r; head[u] = tot++;
to[tot] = u; nxt[tot] = head[v];
vis[tot] = false;
real[tot] = r; head[v] = tot++;
}
}GG;
void euler(int u){
int tag = ++cur[u];
for(int i = GG.head[u]; ~i; i = GG.nxt[i]){
if(GG.vis[i]) continue;
int v = GG.to[i];
GG.vis[i] = GG.vis[i^1] = true;
if(GG.real[i]) ret.push_back(make_pair(u,v));
GG.head[u] = GG.nxt[i];
euler(v);
if(tag!=cur[u]) break;
}
}
void rua(int id){
for(auto e : es[id]) GG.ADDEDGE(e.first,e.second,true);
int last = -1;
for(int x : S[id]){
if(!(deg[x]&1)) continue;
if(last==-1) last = x;
else{
GG.ADDEDGE(x,last,false);
last = -1;
}
}
euler(*S[id].begin());
}
void solve(){
cin >> n >> m;
ret.clear();
for(int i = 0; i <= n; i++){
es[i].clear(); S[i].clear();
deg[i] = belong[i] = cur[i] = 0;
G[i].clear();
}
memset(GG.head,255,sizeof(GG.head));
GG.tot = 0;
for(int i = 1; i <= m; i++){
int u, v; cin >> u >> v;
es[0].push_back(make_pair(u,v));
G[u].push_back(v); G[v].push_back(u);
deg[u]++; deg[v]++;
}
int ans = 0;
for(int i = 1; i <= n; i++) if(!(deg[i]&1)) ans++;
ID = 0;
for(int i = 1; i <= n; i++) if(!belong[i]) getMark(i,++ID);
for(int i = 0; i < m; i++) es[belong[es[0][i].first]].push_back(es[0][i]);
for(int i = 1; i <= ID; i++) rua(i);
cout << ans << endl;
for(auto e : ret)
cout << e.first << ' ' << e.second << endl;
}
int main(){
____();
int t; for(cin >> t; t; t--) solve();
return 0;
}