题意：
给出两个最大团的补图，现在要求增加一条边，使得最大最大团个数增加至少\(1\)。
思路：
- 我们求出团的补图，问题可以转换为：对于一个二分图，选择删掉一条边，能够增大其最大独立集的点集数。
- 然后做法就是考虑在最大流的残余网络上，对容量为\(1\)的边求强连通分量（包含源点、汇点）。
- 若存在一条边\((x,y)\)为匹配边，并且\(x,y\)在不同的强连通分量中，那么\((x,y)\)这条边为必经边，即最大匹配中包含这条边；若\((x,y)\)为非匹配边并且\(x,y\)在同一强连通分量中，那么\((x,y)\)为最大匹配的可行边，即这条边存在于至少一个最大匹配中。
- 证明的话，就拿必经边来说，若\((x,y)\)在同一强连通分量中，我们去掉\(x,y\)这条边，还是有增广路径能从\(x\)到\(y\)，此时最大匹配没变并且\((x,y)\)流量为\(0\)。所以\((x,y)\)不能在同一强连通分量中。
注意一开始要对图进行二分图染色。
代码如下：
#include <bits/stdc++.h>
#define MP make_pair
#define fi first
#define se second
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#ifdef Local
#define dbg(args...) do { cout << #args << " -> "; err(args); } while (0)
void err() { std::cout << '\n'; }
template<typename T, typename...Args>
void err(T a, Args...args) { std::cout << a << ' '; err(args...); }
#else
#define dbg(...)
#endif
void pt() {std::cout << '\n'; }
template<typename T, typename...Args>
void pt(T a, Args...args) {std::cout << a << ' '; pt(args...); }
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
//head
const int N = 5e4 + 5, M = 1e6 + 5;#define INF 0x3f3f3f3f
template <class T>
struct Dinic{
struct Edge{
int v, next;
T flow;
Edge(){}
Edge(int v, int next, T flow) : v(v), next(next), flow(flow) {}
}e[M << 1];
int head[N], tot;
int dep[N];
void init() {
memset(head, -1, sizeof(head)); tot = 0;
}
void adde(int u, int v, T w, T rw = 0) {
e[tot] = Edge(v, head[u], w);
head[u] = tot++;
e[tot] = Edge(u, head[v], rw);
head[v] = tot++;
}
bool BFS(int _S, int _T) {
memset(dep, 0, sizeof(dep));
queue <int> q; q.push(_S); dep[_S] = 1;
while(!q.empty()) {
int u = q.front(); q.pop();
for(int i = head[u]; ~i; i = e[i].next) {
int v = e[i].v;
if(!dep[v] && e[i].flow > 0) {
dep[v] = dep[u] + 1;
q.push(v);
}
}
}
return dep[_T] != 0;
}
T dfs(int _S, int _T, T a) {
T flow = 0, f;
if(_S == _T || a == 0) return a;
for(int i = head[_S]; ~i; i = e[i].next) {
int v = e[i].v;
if(dep[v] != dep[_S] + 1) continue;
f = dfs(v, _T, min(a, e[i].flow));
if(f) {
e[i].flow -= f;
e[i ^ 1].flow += f;
flow += f;
a -= f;
if(a == 0) break;
}
}
if(!flow) dep[_S] = -1;
return flow;
}
T dinic(int _S, int _T) {
T max_flow = 0;
while(BFS(_S, _T)) max_flow += dfs(_S, _T, INF);
return max_flow;
}
stack <int> s;
int dfs_T, num;
int scc[N], dfn[N], low[N];
void Tarjan(int u){
dfn[u] = low[u] = ++dfs_T;
s.push(u);
for(int i = head[u]; i != -1;i = e[i].next){
int v = e[i].v;
if(e[i].flow == 0) continue;
if(!dfn[v]){
Tarjan(v);
low[u] = min(low[u], low[v]);
}else if(!scc[v]){
low[u] = min(low[u], dfn[v]);
}
}
if(low[u] == dfn[u]){
num++; int now;
do{
now = s.top(); s.pop();
scc[now] = num;
}while(!s.empty() && now!=u);
}
}
};
Dinic <int> solve;int n, m;vector <int> g[N];
int col[N];
void color(int u, int c) {
col[u] = c;
for(auto v : g[u]) {
if(!col[v]) color(v, 3 - c);
}
}void run() {
solve.init();
for(int i = 1; i <= m; i++) {
int u, v; cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
for(int i = 1; i <= n; i++) {
if(!col[i]) color(i, 1);
}
int t = 2 * n + 1;
for(int i = 1; i <= n; i++) {
if(col[i] == 1) {
solve.adde(0, i, 1);
for(auto j : g[i]) {
solve.adde(i, j + n, 1);
}
} else {
solve.adde(i + n, t, 1);
}
}
int flow = solve.dinic(0, t);
dbg(flow);
for(int i = 0; i <= t; i++) {
if(!solve.dfn[i]) {
solve.Tarjan(i);
}
}
dbg(solve.num);
vector <pii> ans;
for(int u = 1; u <= n; u++) {
for(int i = solve.head[u]; i != -1; i = solve.e[i].next) {
int v = solve.e[i].v;
if(solve.e[i].flow == 1) continue;
if(v > n && solve.scc[u] != solve.scc[v]) {
int x = u, y = v - n;
if(x > y) swap(x, y);
ans.push_back(MP(x, y));
}
}
}
sort(all(ans), [&](pii A, pii B) {
if(A.fi == B.fi) return A.se < B.se;
return A.fi < B.fi;
});
pt(sz(ans));
for(auto it : ans) cout << it.fi << ' ' << it.se << '\n';
}int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cout << fixed << setprecision(20);
#ifdef Local
freopen("../input.in", "r", stdin);
freopen("../output.out", "w", stdout);
#endif
while(cin >> n >> m) run();
return 0;
}
