/*
 * 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 v;
        list<Edge>::iterator rev_it;
    };

    int NM[2];
    vector<list<Edge>> adj_list_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 (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])
        {
            unsigned int adj_sz = adj_list_lr[nlr][e.v].size();
            if (adj_sz < min_adj_sz)
            {
                min_adj_sz = adj_sz;
                bv = e.v;
            }
        }

        return bv;
    }

    //edges of v to u are not removed here, in order to 
    // avoid duplicated node deletion in lists
    void remove_node_edges_and_edges_to_node(int u, int lr, int v)
    {
        for (Edge& e : adj_list_lr[lr][u])
        {
            if (e.v == v) continue;

            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_v_sz, (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, v;
            {
                //BlockTimerC bc("min size node");
                bool found_ = find_node_min_non_empty_adj_list(u, lr);
                if (!found_) break;
            }
            {
                //BlockTimerC bc("min size neighbor");
                //find the neighbor with the minimum number of edges
                v = find_neighbor_min_adj_list(u, lr);
            }
            {
                //BlockTimerC bc("connect");
                //connect u and v
                if (lr == 0)
                    connections.push_back(make_pair(u, v));
                else
                    connections.push_back(make_pair(v, u));
            }
            {
                //BlockTimerC bc("remove edges");
                //remove the edges of the connected nodes
                remove_node_edges_and_edges_to_node(u, lr, v);
                remove_node_edges_and_edges_to_node(v, 1 - lr, u);
            }
            //cout << '\n';

        }
    }
}

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;
        char line[30];
        const int lz = 30;
        ifs.getline(line, lz);
        int numbers[3] = { 0, 0, 0 };
        int k = 0;
        char c;
        int j = 0;
        while ((c = line[j]) != '\0')
        {
            if ('0' <= c && c <= '9')
                numbers[k] = numbers[k] * 10 + c - '0';
            else
                k++;

            j++;
        }
        N = numbers[0];
        M = numbers[1];
        E = numbers[2];
        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++)
        {
            int u, v;
            //ifs >> u >> v;
            ifs.getline(line, lz);
            int numbers[2] = { 0, 0 };
            char c;
            int j = 0;
            int k = 0;
            while ((c = line[j]) != '\0')
            {
                if ('0' <= c && c <= '9')
                    numbers[k] = numbers[k] * 10 + c - '0';
                else
                    k++;

                j++;
            }
            u = numbers[0];
            v = numbers[1];

            Edge e_;
            adj_list_lr[0][u].push_back(e_);
            adj_list_lr[1][v].push_back(e_);

            Edge& el = adj_list_lr[0][u].back();
            el.v = v;
            //set the iterator and the backward iterator
            el.rev_it = adj_list_lr[1][v].end();
            el.rev_it--;

            Edge& rel = adj_list_lr[1][v].back();
            rel.v = u;
            rel.rev_it = adj_list_lr[0][u].end();
            rel.rev_it--;
        }

        ifs.close();
    }

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

        for (int k = 0; k < 2; k++)
        {
            adj_list_size[k].resize(NM[k] + 1);
            for (int u = 1; u <= NM[k]; u++)
            {
                int adj_sz_k_u = adj_list_size[k][u] = adj_list_lr[k][u].size();
                if (adj_sz_k_u > 0) Q.push(make_pair(adj_sz_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;
}