/*
 * e_020_cuplaj_maxim_v3.cpp
 *
 *  Created on: Jun 7, 2015
 *      Author: Marius
 */

#include <iostream>
#include <fstream>
#include <limits>
#include <vector>
#include <list>
#include <queue>
#include <utility>
using namespace std;

namespace e_020_cuplaj_maxim_v3_nms
{
    int N, M, E;
    typedef pair<int, int> pii;
    
    struct Edge
    {
        int u, lr, v;
        list<Edge>::iterator it, rev_it;
    };
    
    vector<list<Edge>> adj_list_lr[2];
    vector<int> connected_lr[2];
    vector<pii> connections;
    
    priority_queue<pii, vector<pii>, std::greater<pii>> Q;
    
    bool find_node_min_non_empty_adj_list(int& u, int& lr)
    {
        int min_adj_sz = std::numeric_limits<int>::max();

        for (int k = 0; k < 2; k++)
        {
            int nodes = adj_list_lr[k].size() - 1;
            for (int i = 1; i <= nodes; i++)
            {
                if (connected_lr[k][i]) continue; //do not process the connected nodes
                int adj_sz = adj_list_lr[k][i].size();
                //do not process the nodes with no connections, there is nothing to connect
                if (adj_sz == 0) continue;

                if (adj_sz < min_adj_sz)
                {
                    min_adj_sz = adj_sz;
                    u = i;
                    lr = k;
                }
            }
        }

        if (min_adj_sz == std::numeric_limits<int>::max())
            return false;
        else
            return true;
    }

    int find_neighbor_min_adj_list(int u, int lr)
    {
        int nlr = 1 - lr; //the side of the neighbor
        int bv;
        unsigned int min_adj_sz = std::numeric_limits<unsigned int>::max();
        for (Edge& e : adj_list_lr[lr][u])
        {
            if (connected_lr[nlr][e.v]) continue; //do not process the connected nodes

            if (adj_list_lr[nlr][e.v].size() < min_adj_sz)
            {
                min_adj_sz = adj_list_lr[nlr][e.v].size();
                bv = e.v;
            }
        }

        return bv;
    }

    void remove_node_edges_and_edges_to_node(int u, int lr)
    {
        for (Edge& e : adj_list_lr[lr][u])
            adj_list_lr[1 - lr][e.v].erase(e.rev_it);

        adj_list_lr[lr][u].clear();
    }

    void find_bipartite_matching()
    {
        while (1)
        {
            //find the node with the minimum number of edges
            int u, lr;
            bool found_ = find_node_min_non_empty_adj_list(u, lr);
            if (!found_) break;

            //find the neighbor with the minimum number of edges
            int v = find_neighbor_min_adj_list(u, lr);

            //connect u and v
            if (lr == 0)
                connections.push_back(make_pair(u, v));
            else
                connections.push_back(make_pair(v, u));
            connected_lr[lr][u] = 1;
            connected_lr[1 - lr][v] = 1;

            //remove the edges of the connected nodes
            remove_node_edges_and_edges_to_node(u, lr);
            remove_node_edges_and_edges_to_node(v, 1 - lr);
        }
    }
}

//int e_020_cuplaj_maxim_v3_main()
int main()
{
    using namespace e_020_cuplaj_maxim_v3_nms;

    ifstream ifs("cuplaj.in");
    ifs >> N >> M >> E;
    adj_list_lr[0].resize(N + 1);
    adj_list_lr[1].resize(M + 1);

    for (int i = 1; i <= E; i++)
    {
        Edge e;
        ifs >> e.u >> e.v;   
        e.lr = 0; //edge from left to right
        Edge re;
        re.u = e.v; 
        re.v = e.u;
        re.lr = 1;
        
        adj_list_lr[0][e.u].push_back(e);
        adj_list_lr[1][e.v].push_back(re);
        
        Edge& el = adj_list_lr[0][e.u].back();
        //set the iterator and the backward iterator
        el.it = adj_list_lr[0][e.u].end();
        el.it--;
        el.rev_it = adj_list_lr[1][e.v].end();
        el.rev_it--;
        
        Edge& rel = adj_list_lr[1][e.v].back();
        rel.it = el.rev_it;
        rel.rev_it = el.it;
    }

    for (int k = 0; k < 2; k++)
    {
        connected_lr[k].resize(N + 1);
        fill(connected_lr[k].begin(), connected_lr[k].end(), 0);
    }

    ifs.close();

    find_bipartite_matching();

    ofstream ofs("cuplaj.out");
    ofs << connections.size() << endl;
    for (auto& p : connections)
        ofs << p.first << ' ' << p.second << '\n';
    ofs.close();

    return 0;
}

int test_iterators_after_erase_in_list()
//int main()
{
    list<int> l;
    for (int i = 0; i <= 10; i++)
        l.push_back(i);

    for (list<int>::iterator it = l.begin(); it != l.end(); it++)
        cout << it._M_node << " ";
    cout << endl;
    
    list<int>::iterator it = --l.end();    
    cout << it._M_node << endl;

    l.remove(5);
    l.remove(1);
    l.remove(3);

    for (list<int>::iterator it = l.begin(); it != l.end(); it++)
        cout << it._M_node << " ";
    cout << endl;

    cout << it._M_node << endl;
    
    return 0;
}