题解：CF847J Students Initiation

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int N = 2e4+4;
const int inf = 2e9;

struct edge {
	int to,cap,rev;
};

int lvl[N],vis[N];
vector<edge> g[N];

void ae(int u,int v,int w){
	g[u].push_back({v,w,g[v].size()});
	g[v].push_back({u,0,g[u].size()-1});
}

void bfs(int s){
	memset(lvl,-1,sizeof lvl);
	queue<int> q;
	q.push(s),lvl[s]=0;
	while (!q.empty()){
		int u=q.front();
		q.pop();
		for (auto v : g[u]){
			if (v.cap>0 && lvl[v.to]<0){
				lvl[v.to]=lvl[u]+1;
				q.push(v.to);
			}
		}
	}
}

int dfs(int v,int t,int f){
	if (v==t) return f;
	for (int &i=vis[v]; i<g[v].size(); i++){
		edge &e=g[v][i];
		if (e.cap>0 && lvl[v]<lvl[e.to]){
			int d=dfs(e.to,t,min(f,e.cap));
			if (d>0){
				e.cap-=d,g[e.to][e.rev].cap+=d;
				return d;
			}
		}
	}
	return 0;
}

int mf(int s,int t){
	int ans=0;
	while (1){
		bfs(s);
		if (lvl[t]<0) return ans;
		memset(vis,0,sizeof vis);
		int f;
		while ((f=dfs(s,t,inf))>0) ans+=f;
	}
} 

int cnt;

void init(){
	cnt=0;
	for (int i=0; i<N; i++) g[i].clear();
}

int n,m,u[N],v[N],id[N];

bool chk(int mid){
	init();
	int S=0,T=n+1;
	cnt=n+1;
	for (int i=1; i<=n; i++){
		ae(i,T,mid);
	}
	for (int i=1; i<=m; i++){
		int in=(++cnt);
		id[i]=in;
		ae(in,u[i],1);
		ae(in,v[i],1);
		ae(S,in,1);
	}
	int ans=mf(S,T);
	if (ans==m) return 1;
	return 0;
}

void pr(){
	for (int i=1; i<=m; i++){
		auto e=g[id[i]][0];
		if (e.cap) cout<<v[i]<<" "<<u[i]<<"\n";
		else cout<<u[i]<<" "<<v[i]<<"\n";
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin>>n>>m;
	for (int i=1; i<=m; i++){
		cin>>u[i]>>v[i];
	}
	int l=-1,r=m+1;
	while (l+1<r){
		int mid=l+r>>1;
		if (chk(mid)){
			r=mid;
		}
		else l=mid;
	}
	cout<<r<<"\n";
	chk(r);
	pr();
	return 0;
}