【題解】CSES 1696 School Dance

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
 
int n, m, k, a, b, ma[505], vis[505], ans;
vector <int> v[505];
 
bool dfs(int x){
    for (int i:v[x]){
        if (!ma[i]){
            ma[i] = x;
            return 1;
        }
        else if (vis[i]) continue;
        else{
            vis[i] = 1;
            if (dfs(ma[i])){
                ma[i] = x;
                return 1;
            }
        }
    }
    return 0;
}
 
int main() {
    cin >> n >> m >> k;
    for (int i = 0; i < k; i++){
        cin >> a >> b;
        v[a].push_back(b);
    }
    for (int i = 1; i <= n; i++){
        memset(vis, 0, sizeof(vis));
        if (dfs(i)) ans++;
    }
    cout << ans << "\n";
    for (int i = 1; i <= m; i++){
        if (ma[i]){
            cout << ma[i] << " " << i << "\n";
        }
    }
}