import java.io.*;
import java.lang.*;
import java.util.*;
import java.awt.*;
public class MaxParring {
    private static int m = 0;
    private static int n1 = 0;
    private static int n2 = 0;
    private static Node[] v1;
    private static Node[] v2;
    private static int p = 0;
    private static Stack farvedKnuder = new Stack();
    private static Node denSorteKnude;
    
    public static void main(String args[]) {
	//------------------------------------
	long tid = System.currentTimeMillis();
	try {getFile(args[0]);} catch (IOException e)
	    {System.out.println("File not found");}
	
	findMaxParring();
	
	while (findSkifteVej()) {
	    opdaterGraf();
	    farvHvid();
	    findMaxParring();
	}
	
	printPairs();
	vis("-----------------------------");
	vis("V1: "+n1 +"  V2: "+n2);
	vis("Antal kanter: "+m);
	vis("-----------------------------");
	vis("Maksimal antal parringer for " +args[0]+" = "+p);
	vis("");
	vis("Tid: "+(System.currentTimeMillis()-tid));
	//-----------------------------------
    }
    
    public static void getFile(String fileName) throws IOException {
	BufferedReader infile = new BufferedReader( new FileReader(fileName) );
	vis("Indlæser fil "+fileName);
	
	n1 = new Integer(infile.readLine()).intValue();
	n2 = new Integer(infile.readLine()).intValue();
	m  = new Integer(infile.readLine()).intValue();
	v1 = new Node[n1];
	v2 = new Node[n2];
	
	for (int j=0; j<n1; j++)  { v1[j] = new Node(j+"",true); }
	for (int k=0; k<n2; k++)  { v2[k] = new Node(k+"",false); }
	
	for (int i=0; i<m; i++) {
	    StringTokenizer t = new StringTokenizer(infile.readLine()," ");
	    if (t.countTokens() == 2) {
		new Edge(v1[new Integer(t.nextToken()).intValue()],
			 v2[new Integer(t.nextToken()).intValue()]);
	    }
	}
	vis("Færdig med at indlæse fil ("+m+")");
    }
    
    public static void vis(String besked) { System.out.println(besked); }    
    public static void log(String besked) { System.out.print(besked); }
    public static boolean findSkifteVej() { return !(denSorteKnude == null); }
    public static void opdaterGraf() { findKnude(denSorteKnude); }
    
    public static void findKnude(Node knude) {
	if (!((knude.getColor() == 2) && knude.memberv1)) {
  	    findKnude(knude.visitedFrom.from);
	    knude.visitedFrom.skift();	    
	}
    }
    
    public static void farvHvid() {
	denSorteKnude = null;	
        while (!farvedKnuder.empty()) {
	    Edge tmpEdge = (Edge) farvedKnuder.pop();
	    tmpEdge.to.setColor(0);
	    tmpEdge.from.setColor(0);
	}
    }

    public static void findMaxParring() {
	//vis("Finder maxParring");
	for (int i=0;i<n1;i++) {
	    if (v1[i].inDegree()==0) {
		v1[i].setColor(2);
		farvGraf(v1[i]);
	    }
	}
    }
    
    public static void farvGraf(Node knude) {
	if (knude.getColor() == 0) {
	    knude.setColor(1);
	    findKnude(knude);
	    
	}
	
	Enumeration j = knude.outEdges();
	while (j.hasMoreElements()) {
	    Edge kant = (Edge) j.nextElement();
	    Node tilKnude = kant.to;
	    
	    //vis(knude.toString()+ "," +tilKnude.toString());
	    
	    if (tilKnude.getColor() == 0) {
		if ( tilKnude.memberv1 ) {
		    tilKnude.setColor(1);
		    farvedKnuder.push(kant);
		    farvGraf(tilKnude);
		}
		else if ( !tilKnude.memberv1 && tilKnude.outDegree() > 0 ) {
		    tilKnude.setColor(1);
		    farvedKnuder.push(kant);
		    farvGraf(tilKnude);
		}
		else {
		    tilKnude.setColor(2);
		    farvedKnuder.push(kant);
		    denSorteKnude = tilKnude;
		}
		tilKnude.setVisitor(kant);
	    }
	}
    }

    public static void printPairs() {
	for (int i=0; i<v1.length; i++)
	    for (Enumeration e = v1[i].in.elements(); e.hasMoreElements();) {
		Edge edge = (Edge)e.nextElement();
		vis("("+ edge.from + " , " + edge.to +")");
		p++;
	    }
    }
}