CSES - Shared codeLink to this code: https://cses.fi/paste/25fda65b6f4263c369c9b3/
#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
#include<array>
#include<algorithm>
using namespace std;
int graph[1002][1002],par[1002],edges[1002][1002];
bool vis[1002];
bool bfs(){
int u=0;
queue<int>que;
que.push(u);
for(int i=0;i<=1001;i++)vis[i]=0;
while(!que.empty() ){
u=que.front();
que.pop();
if(vis[u])continue;
vis[u]=true;
for(int v=0;v<=1001;v++){
if(!vis[v] and graph[u][v]>0){
par[v]=u;
que.push(v);
}
}
}
return vis[1001];
}
int main(){
int n,m,k,a,b;
cin>>n>>m>>k;
while(k--){
cin>>a>>b;
b+=500;
graph[a][b]=1;
graph[0][a]=1;
graph[b][1001]=1;
edges[a][b]=1;
}
int cnt=0;
while(bfs()){
a=1001;
cnt++;
while(a!=0){
graph[par[a]][a]--;
graph[a][par[a]]++;
a=par[a];
}
}
cout<<cnt<<endl;
vector<array<int,2>>ans;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(!graph[i][j+500] and edges[i][j+500]){
cout<<i<<" "<<j<<endl;
}
}
}
return 0;
}