Codeforces

Luogu

分析

这个“所有边的出入度都是偶数”可以想到欧拉回路。可以发现只要造一张边数最小且为偶数的欧拉图出来，然后把欧拉回路上的边依次正向、反向定向即可。

这个很容易造，我们只要把相邻度数为奇数的点两两之间连一条边即可。练完之后边数可能是奇数，再连一个自环即可。显然这样子边数是最小的。

代码

//  ====================================
//    author: M_sea
//    website: https://m-sea-blog.com/
//  ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10,M=250000+10;

int n,m;

struct edge { int v,nxt; } e[M<<1];
int head[N],deg[N];
void addEdge(int u,int v) {
    static int cnt=1;
    ++deg[u],++deg[v];
    e[++cnt]=(edge){v,head[u]},head[u]=cnt;
    e[++cnt]=(edge){u,head[v]},head[v]=cnt;
}

int vis[M<<1],s=0;
void dfs(int u) {
    for (int& i=head[u];i;i=e[i].nxt) {
        if (vis[i]) continue; vis[i]=vis[i^1]=1;
        int v=e[i].v; dfs(v);
        if (s) printf("%d %d\n",u,v);
        else printf("%d %d\n",v,u);
        s^=1;
    }
}

int main() {
    n=read(),m=read();
    for (int i=1;i<=m;++i) addEdge(read(),read());
    for (int i=1,lst=0;i<=n;++i) {
        if (deg[i]&1) {
            if (!lst) lst=i;
            else ++m,addEdge(lst,i),lst=0;
        }
    }
    if (m&1) ++m,addEdge(1,1);
    printf("%d\n",m);
    dfs(1);
    return 0;
}