给出的图中恰包含2个团，则图的补图为一个二分图，其最大独立集为原图的最大团。
我们知道，二分图的最大独立集=V-最小顶点覆盖，最小顶点覆盖=最大匹配。
问题转化为：计算删去后最大匹配减小的边集。
所以建图跑最大流，对残余网络中的每一条满流边讨论。
这需要用到tarjan：若该满流边的端点同属一个强连通，那么通过该边的增广路不是必须的，这条边就不能算在答案里。
码吧。。 建图时要利用二分图染色。
请务必启用-std=gnu++11开关
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int N=1e4+5;
const int L=5e5+5;
const int inf=0x3f3f3f3f;
int S=N-1,T=N-2;
int head[N],to[L],upp[L],last[L],cnt=1;
int que[N],lev[N],hd,tl;
inline void add_edge(int x,int y,int u1,int u2=0) {
to[++cnt]=y,upp[cnt]=u1,last[cnt]=head[x],head[x]=cnt;
to[++cnt]=x,upp[cnt]=u2,last[cnt]=head[y],head[y]=cnt;
}
inline bool bfs() {
memset(lev,0,sizeof lev);
lev[S]=1;
que[hd=0,tl=1]=S;
while(hd<tl) {
int x=que[++hd];
for(int i=head[x]; i; i=last[i]) if(upp[i]>0 && !lev[to[i]])
lev[to[i]]=lev[x]+1, que[++tl]=to[i];
}
return lev[T]!=0;
}
int dfs(int x,int tf) {
if(x==T) return tf;
int tot=0,tmp;
for(int i=head[x]; i; i=last[i]) if(upp[i]>0 && lev[x]+1==lev[to[i]]) {
tmp=dfs(to[i],min(tf-tot,upp[i]));
if(tmp) upp[i]-=tmp,upp[i^1]+=tmp,tot+=tmp;
if(tot==tf) break;
}
if(!tot) lev[x]=-1;
return tot;
}
int n,m;
vector<int> e[N];
vector<pair<int,int>> ans;
int col[N],low[N],dfn[N],idx;
int sta[N],bel[N],tot,top;
void ran(int x) {
for(int y: e[x]) if(!col[y])
col[y]=3^col[x], ran(y);
}
void pre(int x) {
dfn[x]=low[x]=++idx;
sta[++top]=x;
for(int i=head[x]; i; i=last[i]) if(upp[i]>0) {
if(!dfn[to[i]]) {
pre(to[i]);
low[x]=min(low[x],low[to[i]]);
} else if(!bel[to[i]])
low[x]=min(low[x],dfn[to[i]]);
}
if(dfn[x]==low[x]) {
tot++;
do bel[sta[top]]=tot; while(sta[top--]!=x);
}
}
int main() {
scanf("%d%d",&n,&m);
for(int x,y,i=m; i--; ) {
scanf("%d%d",&x,&y);
e[x].push_back(y);
e[y].push_back(x);
}
for(int i=1; i<=n; ++i) {
if(!col[i]) col[i]=1, ran(i);
}
for(int i=1; i<=n; ++i) {
if(col[i]==1) {
add_edge(S,i,1);
for(int j:e[i]) add_edge(i,j,1);
} else add_edge(i,T,1);
}
while(bfs()) dfs(S,inf);
for(int i=1; i<=n; ++i) {
if(!dfn[i]) pre(i);
}
if(!dfn[S]) pre(S);
if(!dfn[T]) pre(T);
for(int i=2; i<=cnt; i+=2) {
if(upp[i]==0 && bel[to[i]]!=bel[to[i^1]]
&& to[i]!=S && to[i]!=T && to[i^1]!=S && to[i^1]!=T)
ans.push_back(make_pair(to[i],to[i^1]));
}
for(pair<int,int> &p:ans) {
if(p.first>p.second) swap(p.first,p.second);
}
sort(ans.begin(),ans.end());
printf("%llu\n",ans.size());
for(pair<int,int> p:ans) {
printf("%d %d\n",p.first,p.second);
}
return 0;
}