/*
 * e_020_cuplaj_maxim.cpp
 *
 *  Created on: May 29, 2015
 *      Author: Marius
 */

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

namespace e_032_cuplaj_maxim_max_flow_ford_fulkerson_bfs_optimized_nms
{
    struct Edge
    {
        int u, v; // edge u to v
        int c; // the capacity
        int dir; // direction: forward (1) or backward (-1) edge
        Edge* re; // pointer to the reverse edge in the graph
    };

    int find_max_flow_ford_fulkerson(int N, vector<vector<Edge*>>& adj_list)
    {
        int max_flow = 0;

        list<int> Q;
        list<Edge*> QN; // the list of non-saturate edges u-N
        vector<char> touched_queue;
        vector<Edge*> parent_edges;
        touched_queue.resize(N + 1);
        parent_edges.resize(N + 1);
        bool has_s2t_path = true;
        while (has_s2t_path)
        {
            //no node on the path at the beginning
            Q.clear();
            QN.clear();
            std::fill(touched_queue.begin(), touched_queue.end(), 0);
            for (auto& ep : parent_edges)
                ep = 0;
            //find a path from source to sink in the residual graph
            //only edges with positive capacities should be included in the path
            Q.push_back(1);
            touched_queue[1] = 1;
            while (!Q.empty())
            {
                int u = Q.front();
                Q.pop_front();
                for (Edge* e : adj_list[u])
                {
                    int v = e->v;
                    //not already in queue and an edge with positive capacity
                    if (!touched_queue[v] && e->c > 0)
                    {
                        if (v != N)
                        {
                            //put the node in the list
                            Q.push_back(v);
                            touched_queue[v] = 1;
                            parent_edges[v] = e;
                        }
                        else
                        {
                            //We want a complete BFS with non-saturated edges, 
                            //excluding the final node, so we don't add the final node into the BFS.
                            //We save the parent node into a list.
                            QN.push_back(e);
                        }
                    }
                }
            }

            //parse the list of nodes with u-N non-saturated edges
            for (auto en : QN)
            {
                int min_capacity = en->c; //this capacity is non-zero by design
                int node = en->u;
                while (node != 1)
                {
                    Edge* e = parent_edges[node];
                    min_capacity = min(min_capacity, e->c);
                    //check if the capacity of the current node was not already saturated by
                    // another QN edge. if so, break
                    if (min_capacity == 0) break;
                    //go to the parent node
                    node = e->u;
                }

                if (min_capacity > 0)
                {
                    //we have a non-saturated path from N to 1
                    max_flow += min_capacity; //update the max flow

                    //update the capacity of edges in the residual graph
                    en->c -= min_capacity;
                    //also update the reverse edge
                    en->re->c += min_capacity;

                    node = en->u;
                    while (node != 1)
                    {
                        //update the capacity of edges in the residual graph
                        Edge* e = parent_edges[node];
                        e->c -= min_capacity;
                        //also update the reverse edge
                        e->re->c += min_capacity;
                        //go to the parent node
                        node = e->u;
                    }
                }
            }

            if (QN.size() == 0) has_s2t_path = false;
        }

        return max_flow;
    }
}

//int e_032_cuplaj_maxim_max_flow_ford_fulkerson_bfs_optimized()
int main()
{
    using namespace e_032_cuplaj_maxim_max_flow_ford_fulkerson_bfs_optimized_nms;

    string in_file = "cuplaj.in";
    string out_file = "cuplaj.out";

    int NL, NR, E;
    vector<vector<Edge*>> adj_list;

    ifstream ifs(in_file.c_str());
    if (!ifs.is_open())
    {
        cout << "Input file not found" << endl;
        return -1; // no input file
    }
    ifs >> NL >> NR >> E;

    //the total number of nodes: source + nodes left + nodes right + sink
    //id nodes left : 1 + id in file
    //id nodes right : 1 + NL + id_in_file
    int N = 1 + NL + NR + 1;

    adj_list.resize(N + 1);

    for (int k = 1; k <= E; k++)
    {
        //create the forward and it's backward edge
        Edge* e = new Edge;
        Edge* re = new Edge;

        ifs >> e->u >> e->v;
        //adjust the ids of the nodes
        e->u += 1;
        e->v += 1 + NL;
        e->c = 1;
        e->dir = 1;
        e->re = re;

        re->u = e->v;
        re->v = e->u;
        re->c = 0;
        re->dir = -1;
        re->re = e;

        adj_list[e->u].push_back(e);
        adj_list[e->v].push_back(re);
    }

    ifs.close();

    //add nodes from the source 1 to each node of the set V
    for (int i = 1; i <= NL; i++)
    {
        //create the forward and it's backward edge
        Edge* e = new Edge;
        Edge* re = new Edge;
        e->u = 1;
        e->v = 1 + i;
        e->c = 1;
        e->dir = 1;
        e->re = re;

        re->u = e->v;
        re->v = e->u;
        re->c = 0;
        re->dir = -1;
        re->re = e;

        adj_list[e->u].push_back(e);
        adj_list[e->v].push_back(re);
    }

    //add nodes from the nodes in the set R to the sink 1 + NL + NR + 1
    for (int i = 1; i <= NR; i++)
    {
        //create the forward and it's backward edge
        Edge* e = new Edge;
        Edge* re = new Edge;
        e->u = 1 + NL + i;
        e->v = 1 + NL + NR + 1;
        e->c = 1;
        e->dir = 1;
        e->re = re;

        re->u = e->v;
        re->v = e->u;
        re->c = 0;
        re->dir = -1;
        re->re = e;

        adj_list[e->u].push_back(e);
        adj_list[e->v].push_back(re);
    }

    int max_flow = find_max_flow_ford_fulkerson(N, adj_list);
    ofstream ofs(out_file.c_str());
    ofs << max_flow << endl;
    //parse the adjacency list and find the pairs = edges from V to R having flow
    for (int u = 2; u <= 1 + NL; u++)
        for (auto& e : adj_list[u])
            if (e->dir == 1 && e->re->c > 0) //the edge e has flow
                ofs << u - 1 << " " << e->v - 1 - NL << "\n";
    ofs.close();

    //release the memory
    for (int u = 1; u <= N; u++)
        for (vector<Edge*>::iterator it = adj_list[u].begin(); it != adj_list[u].end(); it++)
            delete *it;

    return 0;
}