题目传送门
考虑题目本质是要求每个点的出度入度都是偶数。
转化一下，就是每个点度数为偶数，出度为偶数。（其实这也是一张图存在欧拉回路的充要条件），这里不讲欧拉回路做法。
显然的总边数一定得是偶数，给出一种构造可以说明这是充要条件。
图保证了联通，我们先跑出一颗 DFS 树，然后考虑给非树边随意定向，然后对于每条树边，从下往上看，如果当前点出度为奇数，那么连向父亲，否则连向自己。
由于总边数为偶数，所以根节点出度一定为偶数（其他点出度都为偶数）。
代码十分好写。
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define getchar() (p1 == p2 && (p2 = (p1 = buf1) + fread(buf1, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
char buf1[1 << 23], *p1 = buf1, *p2 = buf1, ubuf[1 << 23], *u = ubuf;
namespace IO
{template<typename T>void read(T &_x){_x=0;int _f=1;char ch=getchar();while(!isdigit(ch)) _f=(ch=='-'?-1:_f),ch=getchar();while(isdigit(ch)) _x=_x*10+(ch^48),ch=getchar();_x*=_f;}template<typename T,typename... Args>void read(T &_x,Args&...others){Read(_x);Read(others...);}const int BUF=20000000;char buf[BUF],to,stk[32];int plen;#define pc(x) buf[plen++]=x#define flush(); fwrite(buf,1,plen,stdout),plen=0;template<typename T>inline void print(T x){if(!x){pc(48);return;}if(x<0) x=-x,pc('-');for(;x;x/=10) stk[++to]=48+x%10;while(to) pc(stk[to--]);}
}
using namespace IO;
const int N = 5e5+10;
int n,m,x,y,head[N],cnt,in[N],T[N],v[N],siz[N],cnt1,cnt2,v1[N<<1],id[N<<1];
struct w
{int to,nxt;
}b[N<<1];
inline void add(int x,int y)
{b[++cnt].nxt = head[x];b[cnt].to = y;head[x] = cnt;
}
void dfs(int x,int y)
{v[x] = 1;for(int i = head[x];i;i = b[i].nxt)if(!v[b[i].to]){v1[id[i]] = 1;dfs(b[i].to,x);}else if(!v1[id[i]]){v1[id[i]] = 1;print(x),pc(' '),print(b[i].to),pc('\n');siz[b[i].to]++;}if(y){if(siz[x]%2==1) print(y),pc(' '),print(x),pc('\n'),siz[x]++; else print(x),pc(' '),print(y),pc('\n'),siz[y]++; }
}
signed main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);read(n),read(m);for(int i = 1;i <= m;i++){read(x),read(y),in[x]++,in[y]++;add(x,y),add(y,x); id[cnt] = id[cnt-1] = cnt1,cnt1++;}for(int i = 1;i <= n;i++)if(in[i]%2==1) T[++cnt2] = i;for(int i = 1;i <= cnt2;i += 2)add(T[i],T[i+1]),add(T[i+1],T[i]),id[cnt] = id[cnt-1] = cnt1,cnt1++,m++;if(m%2 == 1) in[1] += 2,add(1,1),add(1,1),id[cnt] = id[cnt-1] = cnt1,cnt1++,m++;print(m),pc('\n');dfs(1,0);flush();return 0;
}
/*
每个点出度入度都是偶数，构造一个方案，在加尽量少的边使得可以做到
先保证每个点的连边个数是偶数，这个每条边都是两个点in_i+1，然后度数是奇数的一定有偶数个
因为你每次选两个点加一：
点相同，不变
奇偶性不同，翻转不变
奇偶性相同，+-2，还是不变
然后定向是给一个点D_i++
如果每个点度数为偶数，且边数为偶数，那么一定就合法了（证明考虑不断删环递归子问题）
先随意的给度数为奇数的连一下边
如果接下来边数还为奇数，随便来一个自环
考虑定向，我们可以每次找环，T飞就是了
环的话，我们先套路的跑出dfs树，对于非树边随便连边
然后对于树边，如果siz%2=1，那么连父亲，否则父亲连我,siz++
显然所有点合法时，根也合法
*/