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

#ifdef __BLOCK_TIMERS
#include "util/BlockTimer.h"
#else
class BlockTimerC
{
public:
    BlockTimerC(std::string a) : a(a)
    {}
protected:
    std::string a;
};
#endif

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 = -1;
        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 main1();

//int e_020_cuplaj_maxim_v3_main()
int main()
{
    BlockTimerC bc("Total");
    
    return main1();
}

int main1()
{
    using namespace e_020_cuplaj_maxim_v3_nms;

    {
        BlockTimerC bc("Read inputs");

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

        ifs.close();
    }

    {
        BlockTimerC bc("Put the sizes in the priority queue");

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

    {
        BlockTimerC bc("Algorithm");
        find_bipartite_matching();
    }

    {
        BlockTimerC bc("Write result");
        
        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;
}