Description：

给一个图，给图加最少数量的边并给边定向使得每个点入度出度都为偶数。

$1\leqslant n\leqslant10^5$

Solution：

考虑答案的下界是什么，发现奇度数的点一定需要再连一条边，既然这样每个点度数都是偶数，也就是一定存在一个欧拉回路，那么如果欧拉回路长度为奇数，那么就补一个自环，因为这样边的个数为奇数，每个边会贡献一个入度一个出度，所以一定要补成偶数，然后把欧拉回路求出来，这样每个点入度 $=$ 出度，然后我们只要隔一条边反向一个，就可以使得每个点入度和出度都是偶数了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

inline int rd()

{

	register int res = 0,f = 1;

	register char c = getchar();

	while(!isdigit(c))

	{

		if(c == '-')f = -1;

		c = getchar();

	}

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res * f;

}

int n,m;

#define MAXN 100010

#define MAXM 200010

int ind[MAXN];

int cnt = 0;

struct edge

{

	int to,nxt;

	bool tag;

}e[MAXM << 2];

int edgenum = 0;

int lin[MAXN] = {0};

inline void add(int a,int b)

{

	++cnt;

	++ind[a];++ind[b];

	e[edgenum].to = b;e[edgenum].tag = true;e[edgenum].nxt = lin[a];lin[a] = edgenum;++edgenum;

	e[edgenum].to = a;e[edgenum].tag = true;e[edgenum].nxt = lin[b];lin[b] = edgenum;++edgenum;

	return;

}

int s[MAXM << 1],top = 0;

#define R register

void dfs(int k)

{

	for(R int i = lin[k];i != -1;i = e[i].nxt)

	{

		if(e[i].tag)

		{

			e[i].tag = e[i ^ 1].tag = false;

			dfs(e[i].to);

		}

		while(e[i].nxt != -1 && !e[e[i].nxt].tag)e[i].nxt = e[e[i].nxt].nxt;

	}

	s[++top] = k;

	return;

}

int main()

{

	memset(lin,-1,sizeof(lin));

	scanf("%d%d",&n,&m);

	R int a,b;

	for(R int i = 1;i <= m;++i)

	{

		a = rd();b = rd();

		add(a,b);

	}

	R int last = 0;

	for(R int i = 1;i <= n;++i)

	{

		if(ind[i] & 1)

		{

			if(last == 0)last = i;

			else

			{

				add(i,last);

				last = 0;

			}

		}

	}

	if(cnt % 2 == 1)add(1,1);

	dfs(1);

	printf("%d\n",cnt);

	for(R int i = 1;i < top;++i)

	{

		if(i & 1)printf("%d %d\n",s[i],s[i + 1]);

		else printf("%d %d\n",s[i + 1],s[i]);

	}

	return 0;

}