/*
 * e_20_cuplaj_maxim_hopcroft_karp.cpp
 *
 *  Created on: Jun 14, 2015
 *      Author: Marius
 */

#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;

namespace e_20_cuplaj_maxim_hopcroft_karp_nms
{
    int MAXN = 10001;
    int N, M, E;
    vector<vector<int>> G(MAXN); //the graph
    
    //LR_pairs[i] = the pair of the left node i in the right side 
    vector<int> LR_pairs(MAXN), RL_pairs(MAXN);
    vector<bool> visited(MAXN);
    int coupled_edges;
    
    bool pair_up(int left_node)
    {
        if (visited[left_node]) return false;
        visited[left_node] = true;
        //look for direct connections
        for (auto& r_node : G[left_node])
            if (RL_pairs[r_node] == 0) //if right node unmatched, match it
            {
                LR_pairs[left_node] = r_node;
                RL_pairs[r_node] = left_node;
                return true;
            }
        
        //no directed connections, try the alternating path
        // = removing the conflicting edges 
        for (auto& r_node : G[left_node])
            if (pair_up(RL_pairs[r_node]))
            {
                LR_pairs[left_node] = r_node;
                RL_pairs[r_node] = left_node;
                return true;
            }
        
        return false;
    }
    
    void hopcroft_karp()
    {
        bool done = false;
        coupled_edges = 0;
        while (!done)
        {
            done = true;
            
            for (int i = 1; i <= N; i++) visited[i] = false;
            
            for (int i = 1; i <= N; i++)
                if (!LR_pairs[i] && pair_up(i)) coupled_edges++, done = false;                       
        }
    }
}


int main()
{
    using namespace e_20_cuplaj_maxim_hopcroft_karp_nms;
    
    ifstream ifs("cuplaj.in");
    ifs >> N >> M >> E;
    
    for (int i = 1; i <= E; i++)
    {
        int x, y;
        ifs >> x >> y;
        G[x].push_back(y);
    }
    ifs.close();
    
    hopcroft_karp();    
    
    ofstream ofs("cuplaj.out");
    ofs << coupled_edges << '\n';
    for (int i = 1; i <= N; i++)
        if (LR_pairs[i]) ofs << i << ' ' << LR_pairs[i] << '\n';    
    ofs.close();
    
    return 0;
}