CF723E.md

对每个连通块分别处理 度数是奇数的点必然是偶数个 把度数是奇数的点之间连上边，变成偶数度 然后跑欧拉回路即可

//#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;
}