/*
 * 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;
    };

    int NM[2];
    vector<list<Edge>> adj_list_lr[2];
    vector<int> connected_lr[2];
    vector<pii> connections;
    vector<int> adj_list_size[2];

    priority_queue<pii, vector<pii>, std::greater<pii>> Q;

    bool find_node_min_non_empty_adj_list(int& u, int& lr)
    {
        bool found = false;
        while (!found && !Q.empty())
        {
            pii sz_node = Q.top();
            Q.pop();
            int adj_sz = sz_node.first;
            int lr_ = sz_node.second / (N + M);
            int u_ = sz_node.second % (N + M);
            
            if (!connected_lr[lr_][u_] && adj_sz > 0 && adj_sz == adj_list_size[lr_][u_])
            {
                found = true;
                lr = lr_;
                u = u_;
            }
        }
        
        return found;
    }

    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);
            int adj_v_sz = adj_list_size[1 - lr][e.v] = adj_list_lr[1 - lr][e.v].size();
            if (adj_v_sz > 0) Q.push(make_pair(adj_list_size[1 - lr][e.v], (1-lr) * (N + M) + e.v));
        }

        adj_list_lr[lr][u].clear();
        adj_list_size[lr][u] = 0;
    }

    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;
    NM[0] = N;
    NM[1] = M;
    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(NM[k] + 1);
        fill(connected_lr[k].begin(), connected_lr[k].end(), 0);

        adj_list_size[k].resize(NM[k] + 1);
        for (int u = 1; u <= NM[k]; u++)
        {
            adj_list_size[k][u] = adj_list_lr[k][u].size();
            Q.push(make_pair(adj_list_size[k][u], k * (N + M) + u));
        }
    }

    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;
}