MLE 求条

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149#include<bits/stdc++.h>
using namespace std;
const int N=3e5+20,NN=1e4+20;
int to[N],nxt[N],head[NN],cap[N],cur[NN];
int tot;
int s,t;
void add_(int u,int v,int w)
{
	to[tot]=v;
	cap[tot]=w;
	nxt[tot]=head[u];
	head[u]=tot++;
}
void add(int u,int v,int w){add_(u,v,w),add_(v,u,w);}
int n,m,dis[NN];
bool bfs()
{
	queue<int> q;
	memset(dis,0,sizeof dis);
	memcpy(cur,head,sizeof head);
	q.push(s);
	dis[s]=1;
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		for(int j=head[u];~j;j=nxt[j])
		{
			int v=to[j];
			if(cap[j] and !dis[v])
			{
				dis[v]=dis[u]+1;
				q.push(v);
				if(v==t)return 1;
			}
		}
	}
	return 0;
}
int dfs(int u,int cf)
{
	if(u==t)return cf;
	int su=0;
	for(int j=cur[u];~j;j=nxt[j])
	{
		cur[u]=j;
		int v=to[j];
		if(cap[j] and dis[v]==dis[u]+1)
		{
			int k=dfs(v,min(cap[j],cf));
			cf-=k;
			cap[j]-=k;
			cap[j^1]+=k;
			su+=k;
			if(cf==0)break;
		}
	}
	if(su==0)dis[u]=0;
	return su;
}
set<pair<int,int> > st;
int mxflw;
void dinic()
{
	while(bfs())
		mxflw+=dfs(s,0x3f3f3f3f);
}
stack<int> sk;
int dfn[NN],low[NN],idx,bl[NN],vis[NN],cnt;
void tarjan(int u)
{
	dfn[u]=low[u]=++idx;
	sk.push(u);
	vis[u]=1;
	for(int j=head[u];~j;j=nxt[j])
	{
		int v=to[j];
		if(!cap[j])continue;
		if(!dfn[v])
		{
			tarjan(v);
			low[u]=min(low[u],low[v]);
		}
		else if(vis[v])low[u]=min(low[u],dfn[v]);
	}
	if(dfn[u]==low[u])
	{
		int now=sk.top();
		cnt++;
		do
		{
			now=sk.top();
			bl[now]=cnt;
			vis[now]=0;
			sk.pop();
		}
		while(now!=u);
	}
}
vector<int> g[NN];
int cl[NN];
void color(int u,int fa,int clr)
{
	cl[u]=clr;
	for(auto v:g[u])
	{
		if(v==fa)continue;
		color(v,u,clr^1);
	}
}
struct edge
{
	int u,v;
}e[N];
signed main()
{
	memset(head,-1,sizeof head);
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0),cerr.tie(0);
	cin>>n>>m;
	for(int i=1,u,v;i<=m;i++)
	{
		cin>>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);
		e[i]={u,v};
	}
	s=n+1,t=n+2;
	for(int i=1;i<=n;i++)if(!cl[i])color(i,0,0);
	for(int i=1;i<=n;i++)
	{
		if(!cl[i])add(s,i,1);
		else add(i,t,1);
	}
	for(int i=1,u,v;i<=m;i++)
	{
		u=e[i].u,v=e[i].v;
		if(!cl[u])add(u,v,1);
		else add(v,u,1);
	}
	dinic();
	for(int i=1;i<=n+2;i++)
		if(!dfn[i])
			tarjan(i);
	for(int u=1;u<=n;u++)
	{
		for(int j=head[u];~j;j=nxt[j])
		{
			int v=to[j];
			if(!cap[j] and bl[u]!=bl[v] and v!=s and v!=t)
				st.insert({min(u,v),max(u,v)});
		}
	}
	cout<<st.size()<<'\n';
	for(auto [u,v]:st)cout<<u<<' '<<v<<'\n';
}