Maximum Matching Pairs

//Make CSP great again
#include <bits/stdc++.h>
#define TASK "TESTCODE"
using namespace std;
const int N = 5e2;
vector<int> Adj[N + 1];
int n, m, k, Assigned[N + 1], Visited[N + 1], t;
void read()
{
    cin >> n >> m >> k;
    for (int i = 1; i <= k; ++ i)
    {
        int u, v;
        cin >> u >> v;
        Adj[u].push_back(v);
    }
}
bool DFS(int u)
{
    if (Visited[u] != t)
    {
        Visited[u] = t;
    }
    else
    {
        return false;
    }
    for (int v : Adj[u])
    {
        if (!Assigned[v] || DFS(Assigned[v]))
        {
            Assigned[v] = u;
            return true;
        }
    }
    return false;
}
void solve()
{
    int cnt = 0;
    for (int i = 1; i <= n; ++ i)
    {
        ++t;
        cnt += DFS(i);
    }
    cout << cnt << '\n';
    for (int i = 1; i <= m; ++ i)
    {
        if (Assigned[i])
        {
            cout << Assigned[i] << ' ' << i << '\n';
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    if (fopen(TASK".INP", "r"))
    {
        freopen(TASK".INP", "r", stdin);
        //freopen(TASK".OUT", "w", stdout);
    }
    int t = 1;
    bool typetest = false;
    if (typetest)
    {
        cin >> t;
    }
    for (int __ = 1; __ <= t; ++ __)
    {
        //cout << "Case " << __ << ": ";
        read();
        solve();
    }
}