小清新图论题。
题目大概说了个关于 hall 定理的东西，不多赘述了。
先处理 NO，这是好处理的，在跑匈牙利的时候如果失配那就把增广到的点集输出即可。
然后处理 YES，注意到两个紧密的集合合并还是紧密的集合。那么我们考虑对每个左部点 \(u\) 找到最小的包含他的紧密的集合 \(S_u\)，这个东西怎么求呢？考虑到紧密集合显然是完美匹配的，那么我们直接跑这张图，对于点 \(u\)，考虑任意 \(match_v\) 不为 \(u\) 且与 \(u\) 相邻的右部点 \(v\)，显然与这些右部点匹配的点都要加入集合，那么我们考虑将 \(u\) 向所有 \(match_v\) 连一条有向边，那么 \(S_u\) 由一张极大闭合子图组成。考虑先跑一遍传递闭包，过程与 floyd 相似，并不是什么高级的东西。然后缩点，然后同一强连通分量中的点是要一一连边的，显然这是最优方案，对于 DAG 上的其它边 \(x\rightarrow y\)，考虑是否存在 \(z\) 使得 \(x\rightarrow z\rightarrow y\)，若存在则不需要连边，因为这条边是多余的。否则就连。哦对了，一定要把原来匹配好的边加入答案边集。
传递闭包可以用 bitset 实现，所以理论最优复杂度为 \(\mathcal{O}(n^{2.5}+\frac{n^3}{w})\)。但我因为我懒得写 dinic 了，所以写了复杂度更劣的匈牙利，但是可能跑的更快。
代码：
#include <bits/stdc++.h>
#define rep(i, l, r) for (int i (l); i <= (r); ++ i)
#define rrp(i, l, r) for (int i (r); i >= (l); -- i)
#define pii pair <int, int>
#define eb emplace_back
#define ls p << 1
#define rs ls | 1
using namespace std;
constexpr int N = 1e3 + 5;
typedef unsigned long long ull;
typedef long long ll;
inline int rd () {
int x = 0, f = 1;
char ch = getchar ();
while (! isdigit (ch)) {
if (ch == '-') f = -1;
ch = getchar ();
}
while (isdigit (ch)) {
x = (x << 1) + (x << 3) + ch - 48;
ch = getchar ();
}
return x * f;
}
vector <int> e[N];
int n, m;
bool vis[N << 1];
int match[N << 1];
bool dfs (int u) {
for (auto v : e[u]) {
if (vis[v]) continue; vis[v] = 1;
if (! match[v] || dfs (match[v])) {
match[v] = u;
match[u] = v;
return 1;
}
} return 0;
}
int S[N], tot;
vector <int> G[N], vec[N];
bitset <N> A[N], B[N], E[N], f[N];
int stk[N], top;
int col[N], cnt;
int dfn[N], low[N], tim;
void tarjan (int u) {
stk[++ top] = u, vis[u] = 1;
dfn[u] = low[u] = ++ tim;
for (auto v : G[u]) {
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]) {
int k = 0; ++ cnt;
while (k ^ u) {
k = stk[top --]; vis[k] = 0;
col[k] = cnt;
}
}
}
vector <pii> ans;
int main () {
// freopen ("1.in", "r", stdin);
// freopen ("1.out", "w", stdout);
n = rd (), m = rd ();
rep (i, 1, m) {
int u = rd (), v = rd ();
e[u].eb (v);
}
rep (i, 1, n) {
if (! dfs (i)) {
rep (j, n + 1, n * 2) if (vis[j]) {
S[++ tot] = match[j];
}
S[++ tot] = i;
puts ("NO");
printf ("%d\n", tot);
rep (i, 1, tot) printf ("%d ", S[i]);
return 0;
}
memset (vis, 0, sizeof vis);
}
puts ("YES");
rep (u, 1, n) {
f[u][u] = 1;
for (auto v : e[u]) {
if (match[v] && match[v] != u) {
G[u].eb (match[v]); f[u][match[v]] = 1;
}
}
ans.eb (pii (u, match[u]));
}
rep (j, 1, n) {
rep (i, 1, n) {
if (f[i][j]) f[i] |= f[j];
}
}
rep (i, 1, n) if (! dfn[i]) tarjan (i);
rep (i, 1, n) vec[col[i]].eb (i);
rep (i, 1, cnt) {
if (vec[i].size () == 1) continue;
for (int j = 0; j < vec[i].size (); ++ j) {
ans.eb (pii (vec[i][j], match[vec[i][(j + 1) % vec[i].size ()]]));
}
}
rep (u, 1, n) for (auto v : G[u]) if (col[u] ^ col[v]) E[col[u]][col[v]] = 1;
rep (i, 1, cnt) A[i][i] = B[i][i] = 1;
rep (i, 1, n) {
rep (j, 1, n) {
if (f[i][j]) {
A[col[i]][col[j]] = B[col[j]][col[i]] = 1;
}
}
}
rep (i, 1, cnt) {
rep (j, 1, cnt) {
if (! E[i][j]) continue;
if ((A[i] & B[j]).count () == 2) {
ans.eb (pii (vec[i][0], match[vec[j][0]]));
}
}
}
printf ("%ld\n", ans.size ());
for (auto p : ans) printf ("%d %d\n", p.first, p.second);
}