Description：

给一个图包含两个团，求填上哪些边可以使得某一个团的大小增大。

$1\leqslant n\leqslant10000$

Solution：

残量网络有这样一个性质，就是缩完点后是一个以 $T$ 为起点 $S$ 为终点的 $DAG$ 。

按照最大团处理的常用方法，先补图转化，既然题目保证了可以用两个团覆盖整个图，那么最后是一个二分图，补图最大独立集 $=$ 原图最大团。

由 $K\ddot onig$ 定理得二分图最大独立集 $=n-$ 最大匹配，也就是说求删掉那些边可以使得最大匹配减少，这些边就是一定在最大匹配上的边，如果把残量网络找出来，判断一条边去掉后是否会使最大流减小只要他们不在同一强连通分量中，这条边就不可替代，所以跑一个 $tarjan$ 即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<vector>

#include<cctype>

#include<cstring>

using namespace std;

#define R register

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 10010

#define MAXM 150010

struct edges

{

	int u,v;

}es[MAXM];

struct edge

{

	int to,nxt,f,tag;

}e[(MAXN + MAXM) * 2];

int edgenum = 0;

int lin[MAXN] = {0};

inline void add(int a,int b,int f)

{

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

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

	return;	

}

vector<int> g[MAXN];

bool v[MAXN];

int c[MAXN];

void dfs(int k,int col)

{

	v[k] = true;c[k] = col;

	for(R vector<int>::iterator it = g[k].begin();it != g[k].end();++it)

	{

		if(v[*it])continue;

		dfs(*it,col ^ 1);

	}

	return;

}

int s,t;

int ch[MAXN];

bool BFS()

{

	queue<int> q;q.push(s);

	memset(ch,-1,sizeof(ch));ch[s] = 0;

	while(!q.empty())

	{

		int k = q.front();q.pop();

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

		{

			if(ch[e[i].to] == -1 && e[i].f)

			{

				ch[e[i].to] = ch[k] + 1;

				q.push(e[i].to);

			}

		}

	}

	return (ch[t] != -1);

}

int flow(int k,int f)

{

	if(k == t)return f;

	int r = 0;

	for(int i = lin[k];i != -1 && f > r;i = e[i].nxt)

	{

		if(ch[e[i].to] == ch[k] + 1 && e[i].f)

		{

			int l = flow(e[i].to,min(e[i].f,f - r));

			r += l;e[i].f -= l;e[i ^ 1].f += l; 

		}

	}

	if(r == 0)ch[k] = -1;

	return r;

}

#define INF 0x3f3f3f3f

void dinic()

{

	while(BFS())while(flow(s,INF));

	return;

}

int dfn[MAXN],low[MAXN],tot = 0;

int st[MAXN],top = 0;

int ins[MAXN],scc = 0;

void tarjan(int k)

{

	dfn[k] = low[k] = ++tot;

	v[k] = true;st[++top] = k;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(!e[i].f)continue;

		if(dfn[e[i].to] == 0)

		{

			tarjan(e[i].to);

			low[k] = min(low[k],low[e[i].to]);

		}

		else if(v[e[i].to])

		{

			low[k] = min(low[k],dfn[e[i].to]);

		}

	}

	if(dfn[k] == low[k])

	{

		int t;

		++scc;

		do

		{

			t = st[top--];

			ins[t] = scc;v[t] = false;

		}while(t != k);

	}

	return;

}

int ans = 0;

pair<int,int> res[MAXM];

int main()

{

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

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

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

	{

		es[i].u = rd();es[i].v = rd();

		g[es[i].u].push_back(es[i].v);

		g[es[i].v].push_back(es[i].u);

	}

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

	{

		if(!v[i])dfs(i,0);

	}

	s = n + 1;t = s + 1;

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

	{

		if(c[i])add(s,i,1);

		else add(i,t,1);

	}

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

	{

		if(c[es[i].u])add(es[i].u,es[i].v,1);

		else add(es[i].v,es[i].u,1);

	}

	dinic();

	memset(v,false,sizeof(v));

	for(int i = 1;i <= t;++i)

	{

		if(dfn[i] == 0)tarjan(i);

	}

	for(int k = 1;k <= n;++k)

	{

		for(int i = lin[k];i != 0;i = e[i].nxt)

		{

			if(e[i].tag && e[i].f == 0 && ins[k] != ins[e[i].to] && e[i].to != s && e[i].to != t)

			{

				++ans;

				res[ans] = make_pair(k,e[i].to);

				if(res[ans].first > res[ans].second)swap(res[ans].first,res[ans].second);

			}

		}

	}

	sort(res + 1,res + 1 + ans);

	cout << ans << endl;

	for(int i = 1;i <= ans;++i)

	{

		printf("%d %d\n",res[i].first,res[i].second);

	}

	return 0;

}