/* @author Søren Munk (u001614) & Mads Peter Lindberg (u001990)
 * @version 1 d. 7/5-2001
 */

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 int progress = 0;
    private static Stack farvedKnuder = new Stack();//oversigt over farvede knuder
    private static Node denSorteKnude;               
    

    /** main-metoden finder maximal parring for grafen specificeret i args[0]
     */
    public static void main(String args[]) {
	//------------------------------------
	vis("-----------------------------");
	long tid = System.currentTimeMillis();
	vis("Henter filen fra disk");
	try {getFile(args[0]);} catch (IOException e)
	    { vis("Filen blev ikke fundet, File not found"); }
	vis("-----------------------------");
	vis("Finder maximal parring");
	findSkifteVej();
	
	while (findesSkifteVej()) {
	    System.out.print((progress)+" gennemløb\r");
	    opdaterGraf();
	    farvHvid();
	    findSkifteVej();
	}
	
	printPairs();
	vis("-----------------------------");
	vis("V1: "+n1 +" V2: "+n2);
	vis("Antal kanter: "+m);
	vis("-----------------------------");
	vis("Størst mulig parringer for "+args[0]+" = "+p);
	vis("Gennemløb grafen "+progress+" gange på "+
	    "["+(System.currentTimeMillis()-tid)+ " milisekunder]");
	//-----------------------------------
    }
    
    /**getFile henter en fil indeholdende en to-delt graf 
     * @param fileName filen der skal hentes ind 
     */ 
    public static void getFile(String fileName) throws IOException {
	BufferedReader infile = new BufferedReader( new FileReader(fileName) );
	vis("Indlæser fil "+fileName);
	//læser fra filen n1,n2,m 
	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); }
	//henter tallene ud
	for (int i=0; i<m; i++) {
	    StringTokenizer t = new StringTokenizer(infile.readLine()," ");
	    if (t.countTokens() == 2) {
		//laver kanterne
		new Edge(v1[new Integer(t.nextToken()).intValue()],
			 v2[new Integer(t.nextToken()).intValue()]);
	    }
	}
	vis("Færdig med at indlæse fil ("+m+" kanter oprettet)");
    }

    /**vis udskriver tekst til consolen
     * @param besked teksten der skal udskrives
     */
    public static void vis(String besked) { System.out.println(besked); }    

    /**findesSkifteVej undesøger om der er en skiftevej 
     * @return sandhedsværdi om der findes en skiftevej
     */
    public static boolean findesSkifteVej() { return !(denSorteKnude == null); }

    /**opdaterGraf finder vej til initialknude 
     */ 
    public static void opdaterGraf() { findKnude(denSorteKnude); }

    /**findKnude finder vej til initialknude rekursivt
     * @param knude en knude amen
     */
    public static void findKnude(Node knude) {
	if (!((knude.getColor() == 2) && knude.memberv1)) {
  	    //den følger vejen tilbage til initialknuden
	    findKnude(knude.visitedFrom.from);
	    //vender pilene på kanterne
	    knude.visitedFrom.skift();
	}
    }

    /**farvhvid farver alle farvede knuder hvide
     */ 
    public static void farvHvid() {
	denSorteKnude = null;	
        //sålænge der er farvede knuder
	while (!farvedKnuder.empty()) {
	    //kantens ender farves hvide
	    Edge tmpEdge = (Edge) farvedKnuder.pop();
	    tmpEdge.to.setColor(0);
	    tmpEdge.from.setColor(0);
	}
    }

    /**findSkifteVej finder alle initialknuder og farver ud fra dem
     */ 
    public static void findSkifteVej() {
	for (int i=0;i<n1;i++) {
	    if (v1[i].inDegree()==0) {
		v1[i].setColor(2);
		farvGraf(v1[i]);
	    }
	}
    }
    
    /**farvGraf farver grafen
     * @param knude knuden der skal farves
     */ 
    public static void farvGraf(Node knude) {
	progress++;
	if (knude.getColor() == 0) {
	    knude.setColor(1);
	    //findKnude(knude);
	}
	//alle knuder fra udgående kanter farves
	Enumeration j = knude.outEdges();
	while (j.hasMoreElements()) {
	    Edge kant = (Edge) j.nextElement();
	    Node tilKnude = kant.to;
	    
		//farver iflg transitionssystemet
		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);
		}
	    }
    }
    
    /**printPairs udskriver alle parringerne
     */ 
    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.toString());
		p++;
	    }
    }
}