school-dance-tarche

#include <bits/stdc++.h>

using namespace std;

struct State {
    vector<vector<int>> ady;
    vector<int> match;
    vector<bool> visited;
};

int augPath(State& state, int k) {
    if (state.visited[k])
        return 0;
    state.visited[k] = true;

    for (auto a : state.ady[k]) {
        if (!state.match[a] || augPath(state, state.match[a])) {
            state.match[a] = k;
            return 1;
        }
    }

    return 0;
}

int main() {
    int n, m, k;
    cin >> n >> m >> k;

    State state;
    state.ady.resize(n + m + 1);
    state.match.resize(n + m + 1);
    state.visited.resize(n + m + 1);

    for (int i = 0; i < k; i++) {
        int a, b;
        cin >> a >> b;
        b += n;
        state.ady[a].push_back(b);
        state.ady[b].push_back(a);
    }

    int ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= n; j++)
            state.visited[j] = false;

        ans += augPath(state, i);
    }

    cout << ans << '\n';
    for (int i = n + 1; i <= n + m; i++) {
        if (state.match[i])
            cout << state.match[i] << ' ' << i - n << '\n';
    }
}