被诈骗了一个上午啊！但是想到了还是很妙的！
每个点至少要保留 条边，也就是一半左右。如果我们直接分配每个点，哪些边选哪些不选，发现这会影响很多东西，无法保证正确。
于是展开联想，选一半，如果有一条路径经过，入边和出边不同，是否就能满足条件了呢？
于是有一个初步的做法，每次 dfs 这个图，将路径上的边黑白交替染色。最后黑色边为答案。
但是有一个问题：如果有奇数度点怎么办？
再想想：一进一出，想到欧拉路。每次从一个奇数度点开始 dfs，一定会在另一个奇数度点结束。每次强制使第一条和最后一条边为黑，这样最多会比原来多 条黑边，最后在对只有偶数度的点的图 dfs 一遍。原来最多会有 ，加起来正好是 的！
在写这篇题解的时候突然产生了一个疑问：如果奇数度点数量顶满会不会出问题？事实上如果顶满了，最后那一遍 dfs 就不会进行，所以是没问题的。
非常巧（zha）妙（pian）的构造！非常好写。
code：
int n,m,deg[N];
bool vis[N],ans[N],pd[N];
vector<pii> g;
int tot,head[N];
struct node{
int to,nxt;
}e[N<<1];
il void add(int u,int v){
e[++tot]={v,head[u]},head[u]=tot;
}
void dfs(int u,int fl,int s,int lst){
for(int &i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(vis[(i+1)/2]){
continue;
}
vis[(i+1)/2]=1;
ans[(i+1)/2]=fl;
dfs(v,fl^1,s,(i+1)/2);
return;
}
pd[u]=1;
if(u!=s){
ans[lst]=1;
}
}
void Yorushika(){
scanf("%d%d",&n,&m);
rep(i,1,m){
int u,v;scanf("%d%d",&u,&v);
add(u,v),add(v,u);
deg[u]++,deg[v]++;
}
rep(i,1,n){
if((deg[i]&1)&&!pd[i]){
dfs(i,1,i,0);
}
}
rep(i,1,n){
while(head[i]){
dfs(i,1,i,0);
}
}
rep(i,1,m){
if(ans[i]){
g.eb(e[i+i-1].to,e[i+i].to);
}
}
printf("%d\n",g.size());
for(auto [u,v]:g){
printf("%d %d\n",u,v);
}
}
signed main(){
int t=1;
// scanf("%d",&t);
while(t--)
Yorushika();
}
