good problem，bad round。
判断 YES 还是 NO 很trivial，就直接跑最大匹配看看是不是 \(n\) 即可。
如果是 NO，那么考虑 Hall 定理的证明过程构造即可。具体方法就是找到左部任意一非匹配点，在残量网络上 BFS 可以到达的点，那所有可以到达的左部点形成的集合就是符合要求的反例。因为你肯定不会 BFS 到右部的非匹配点，而对于右边的匹配点，它左边的匹配点也一定在里面。
重点在于 YES 部分的求解。先发现一个很重要的性质：两个 Tight 集合的并也是 Tight 集合，证明是 trivial 的。因此考虑对每个左部点 \(i\) 找到最小的包含 \(i\) 的 Tight 集合 \(S_i\)，那么两张图等价当且仅当所有 \(S_i\) 均相同。考虑找 \(S_i\) 的过程，显然是依次扩展左右部点集合直到它们相同。这里有一步很牛逼的图论转化我没有想到：对于每个左部点 \(i\) 以及右部点 \(j\) 满足 \(i,j\) 有边且 \(j\ne mch_i\)，连一条 \(i\to mch_j\) 的边，这样 \(S_i\) 就是这张图上 \(i\) 能到达的点集。而二分图边数就是这张图中边数 \(+n\)，因此问题进一步被规约为，找一张边数最小的图满足其传递闭包与原图相同，这个比较好做，先 bitset 做传递闭包，然后强连通分量缩个点，强连通分量内部连个环，外部的边就考虑是否存在一个中间点 \(z\) 满足存在 \(x\to z,z\to y\) 的路径，如果存在就把 \(x\to y\) 边删掉，同样可以 bitset 实现。
时间复杂度 \(n^{2.5}+\dfrac{n^3}{\omega}\)。
const int MAXN=1000;
const int MAXV=2000;
const int MAXE=3e6;
const int INF=0x3f3f3f3f;
int n,m,S,T,hd[MAXV+5],to[MAXE+5],nxt[MAXE+5],cap[MAXE+5],ec=1;
void adde(int u,int v,int f){
to[++ec]=v;cap[ec]=f;nxt[ec]=hd[u];hd[u]=ec;
to[++ec]=u;cap[ec]=0;nxt[ec]=hd[v];hd[v]=ec;
}
int dep[MAXV+5],now[MAXV+5];
bool getdep(){
queue<int>q;memset(dep,-1,sizeof(dep));q.push(S);dep[S]=0;
while(!q.empty()){
int x=q.front();q.pop();now[x]=hd[x];
for(int e=hd[x];e;e=nxt[e]){
int y=to[e],z=cap[e];
if(z&&!~dep[y]){dep[y]=dep[x]+1;q.push(y);}
}
}return ~dep[T];
}
int getflow(int x,int f){
if(x==T)return f;int ret=0;
for(int &e=now[x];e;e=nxt[e]){
int y=to[e],z=cap[e];
if(z&&dep[y]==dep[x]+1){
int w=getflow(y,min(f-ret,z));
ret+=w;cap[e]-=w;cap[e^1]+=w;
if(f==ret)return ret;
}
}return ret;
}
int dinic(){int ret=0;while(getdep())ret+=getflow(S,INF);return ret;}
int mch[MAXV+5];
vector<int>g[MAXN+5],pt[MAXN+5];
bitset<MAXN+5>can[MAXN+5],A[MAXN+5],B[MAXN+5];
int dfn[MAXN+5],low[MAXN+5],vis[MAXN+5],stk[MAXN+5],tp,cmp,tim,bel[MAXN+5];
set<int>out[MAXN+5];
void tarjan(int x){
dfn[x]=low[x]=++tim;stk[++tp]=x;vis[x]=1;
for(int y:g[x]){
if(!dfn[y])tarjan(y),chkmin(low[x],low[y]);
else if(vis[y])chkmin(low[x],dfn[y]);
}
if(dfn[x]==low[x]){
cmp++;int o;
do{o=stk[tp--];vis[o]=0;bel[o]=cmp;}while(o^x);
}
}
int main(){
scanf("%d%d",&n,&m);S=n*2+1;T=n*2+2;
for(int i=1;i<=n;i++)adde(S,i,1),adde(i+n,T,1);
for(int i=1,u,v;i<=m;i++)scanf("%d%d",&u,&v),adde(u,v,1);
if(dinic()!=n){
puts("NO");
static bool in[MAXV+5];
for(int i=1;i<=n;i++)for(int e=hd[i];e;e=nxt[e])if(to[e]==S&&!cap[e]){
queue<int>q;static bool vis[MAXV+5];
vis[i]=1;q.push(i);
while(!q.empty()){
int x=q.front();q.pop();
for(int e=hd[x];e;e=nxt[e])if(cap[e]&&to[e]!=S&&to[e]!=T&&!vis[to[e]])
vis[to[e]]=1,q.push(to[e]);
}
vector<int>vec;
for(int j=1;j<=n;j++)if(vis[j])vec.pb(j);
printf("%d\n",vec.size());
for(int x:vec)printf("%d ",x);printf("\n");
return 0;
}
}
puts("YES");
for(int i=1;i<=n;i++)for(int e=hd[i];e;e=nxt[e])
if(to[e]!=S&&cap[e^1])mch[i]=to[e],mch[to[e]]=i;
// for(int i=1;i<=n*2;i++)printf("%d%c",mch[i]," \n"[i==n*2]);
for(int i=1;i<=n;i++)for(int e=hd[i];e;e=nxt[e])
if(to[e]!=S&&cap[e]){
// printf("%d->%d\n",i,mch[to[e]]);
g[i].pb(mch[to[e]]);can[i][mch[to[e]]]=1;
}
for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)if(can[i][k])can[i]|=can[k];
for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i);
for(int i=1;i<=n;i++)pt[bel[i]].pb(i);
vector<pii>E;
for(int i=1;i<=cmp;i++)if(pt[i].size()>1){
for(int j=1;j<pt[i].size();j++)E.pb(mp(pt[i][j-1],pt[i][j]));
E.pb(mp(pt[i].back(),pt[i][0]));
}
for(int i=1;i<=n;i++)for(int j:g[i])if(bel[i]!=bel[j])out[bel[i]].insert(bel[j]);
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(can[i][j])
A[bel[i]][bel[j]]=B[bel[j]][bel[i]]=1;
for(int i=1;i<=cmp;i++)A[i][i]=B[i][i]=1;
for(int i=1;i<=cmp;i++)for(int j:out[i])if((A[i]&B[j]).count()==2)
E.pb(mp(pt[i][0],pt[j][0]));
printf("%d\n",E.size()+n);
for(pii p:E)printf("%d %d\n",p.fi,mch[p.se]);
for(int i=1;i<=n;i++)printf("%d %d\n",i,mch[i]);
return 0;
}