题意：
分析：
据说是典型题，我好菜还是不会
题意转化一下，相当于每次找一条边，使得加上这条边之后，原图的最大团点数至少+1 , 乍一看没什么想法，但是题目又给出了一个条件，那就是保证原图最多可以被划分为两个最大团 ，又因为原图的最大团=补图的最大独立集=总点数-最小点覆盖数=总点数-补图最大匹配，所以我们要求的东西就转化为和补图最大匹配有关，而原图的补图就是一张二分图，所以我们要求的就是在这张二分图上，删掉哪条边会使得最大匹配至少减少 (1) ,即二分图的最大匹配必经边
好像是一种经典题，没做过/kk
具体做法就是，先跑一遍最大流，然后对于残量网络跑 (tarjan) ，枚举每一条满流的边，看一下它连接的两个点是不是在一个强连通分量里面
感性理解一下就是，对于 (u o v) 这条边，如果 (u,v) 在一个(scc) 里面，那么残量网络里面，一定有一条或几条边可以代替这条满流的边，所以它不是必经边
代码：
#include<bits/stdc++.h>
#define pii pair<int,int>
#define mk(x,y) make_pair(x,y)
#define lc rt<<1
#define rc rt<<1|1
#define pb push_back
#define fir first
#define sec second
using namespace std;
namespace zzc
{
inline int read()
{
int x=0,f=1;char ch=getchar();
while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;
}
const int maxn = 1e4+5;
const int maxm = 3e5+5;
const int inf = 0x3f3f3f;
int n,m,st,top,cnt=1,ed,idx,scc;
int head[maxn],dep[maxn],dfn[maxn],low[maxn],sta[maxn],col[maxn],bel[maxn];
bool vis[maxn];
vector<int> g[maxn];
vector<pii> ans;
queue<int> q;
struct edge
{
int to,nxt,w;
}e[maxm];
void add(int u,int v,int w)
{
e[++cnt].to=v;
e[cnt].w=w;
e[cnt].nxt=head[u];
head[u]=cnt;
}
void add_edge(int u,int v,int w)
{
add(u,v,w);add(v,u,0);
}
void paint(int u,int c)
{
col[u]=c;
for(auto v:g[u]) if(!col[v]) paint(v,c*-1);
}
bool bfs()
{
for(int i=st;i<=ed;i++) dep[i]=-1;
q.push(st);dep[st]=0;
while(!q.empty())
{
int u=q.front();q.pop();
for(int i=head[u];i;i=e[i].nxt)
{
int v=e[i].to;
if(e[i].w&&dep[v]==-1)
{
dep[v]=dep[u]+1;
q.push(v);
}
}
}
return dep[ed]!=-1;
}
int dfs(int u,int flow)
{
if(u==ed) return flow;
int used=0,w;
for(int i=head[u];i;i=e[i].nxt)
{
int v=e[i].to;
if(e[i].w&&dep[v]==dep[u]+1)
{
w=dfs(v,min(e[i].w,flow-used));
e[i].w-=w;
e[i^1].w+=w;
used+=w;
if(used==flow) return used;
}
}
if(!used) dep[u]=-1;
return used;
}
void dinic()
{
while(bfs()) dfs(st,inf);
}
void tarjan(int u)
{
dfn[u]=low[u]=++idx;
sta[++top]=u;
vis[u]=true;
for(int i=head[u];i;i=e[i].nxt)
{
int v=e[i].to;
if(!e[i].w) 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(low[u]==dfn[u])
{
scc++;
do
{
vis[sta[top]]=false;
bel[sta[top]]=scc;
}
while(sta[top--]!=u);
}
}
void work()
{
int a,b;
n=read();m=read();st=0;ed=n+1;
for(int i=1;i<=m;i++)
{
a=read();b=read();
g[a].pb(b);g[b].pb(a);
}
for(int i=1;i<=n;i++) if(!col[i]) paint(i,1);
for(int i=1;i<=n;i++)
{
if(col[i]==1)
{
add_edge(st,i,1);
for(auto v:g[i]) add_edge(i,v,1);
}
else add_edge(i,ed,1);
}
dinic();
for(int i=st;i<=ed;i++) if(!dfn[i]) tarjan(i);
for(int u=1;u<=n;u++)
{
if(col[u]==1)
{
for(int i=head[u];i;i=e[i].nxt)
{
int v=e[i].to;
if(col[v]==-1&&!e[i].w&&bel[u]!=bel[v]) ans.pb(u<v?mk(u,v):mk(v,u));
}
}
}
sort(ans.begin(),ans.end());
printf("%d
",(int)ans.size());
for(auto i:ans) printf("%d %d
",i.fir,i.sec);
}
}
int main()
{
zzc::work();
return 0;
}