//
// Toolkit constraint encoding
//
import java.io.*;
import java.util.*;
import static choco.Choco.*;
import choco.cp.model.CPModel;
import choco.cp.solver.CPSolver;
import choco.kernel.model.Model;
import choco.kernel.solver.Solver;
import choco.kernel.model.variables.integer.IntegerVariable;
import choco.kernel.solver.variables.integer.IntDomainVar;
import choco.kernel.solver.ContradictionException;
import choco.cp.solver.search.integer.varselector.StaticVarOrder;

public class SR {	
   
    int n;
    int[][] pref; // preference of agent_i for agent_j is pref[i][j]
    int[][] rank; // agent in postion j in agent_i's preference list is rank[i][j]
    Model model;
    Solver solver;
    IntegerVariable[] agent; // domain of preferences, last is unmatched
    long totalTime, modelTime, solveTime, readTime, modelSize;
    boolean search;

    SR(String fname) throws IOException {
	search      = true;
	totalTime   = System.currentTimeMillis();
	readTime    = System.currentTimeMillis();
	Scanner sc  = new Scanner(new File(fname));
	n           = sc.nextInt();
	pref        = new int[n][n]; // preference of agent_i for agent_j is pref[i][j]
	rank        = new int[n][n]; // agent in postion j in agent_i's preference list is rank[i][j]
	for (int i=0;i<n;i++){
	    for (int k=0;k<n-1;k++){
		int j = sc.nextInt() - 1; // zero based
		pref[i][j] = k;           // agent_i's preference for agent_j is k
		rank[i][k] = j;           // k^th preference of agent_i is agent_j
	    }
	    rank[i][n-1] = i;             // unmatched if matched to self
	    pref[i][i]   = n-1;
	}
	sc.close();
	readTime = System.currentTimeMillis() - readTime; 
    }

    void build(){
	modelTime = System.currentTimeMillis();
	model     = new CPModel(); 
	agent     = makeIntVarArray("agent",n,0,n-1); // domain of preferences, last is unmatched
	for (int i=0;i<n-1;i++)
	    for (int j=i+1;j<n;j++){
		model.addConstraint(implies(gt(agent[i],pref[i][j]),lt(agent[j],pref[j][i])));
		model.addConstraint(implies(gt(agent[j],pref[j][i]),lt(agent[i],pref[i][j])));
		model.addConstraint(ifOnlyIf(eq(agent[i],pref[i][j]),eq(agent[j],pref[j][i])));
	    }
	solver     = new CPSolver(); 
	solver.read(model); 
	modelTime  = System.currentTimeMillis() - modelTime;
	modelSize  = (Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory())/1024; // kilobytes
    }

    void solve(String command) throws ContradictionException {
	solveTime = System.currentTimeMillis();
	solver.setVarIntSelector(new StaticVarOrder(solver.getVar(agent)));
	if (command.equals("count")){ // count all solutions
	    solver.solve(true);
	    System.out.println("solutions: "+ solver.getNbSolutions());
	}
	else if (command.equals("all")){ // enumerate all solutions
	    if (solver.solve().booleanValue()){
		displayMatching();
		while (solver.nextSolution().booleanValue()) displayMatching();
	    }
	}
	else if (command.equals("propagate")){
	    search = false;
	    try{solver.propagate(); displayPhase1Table();} catch (ContradictionException e){displayPhase1Table();}
	}
	else if (solver.solve().booleanValue()) displayMatching();
	solveTime = System.currentTimeMillis() - solveTime;
	totalTime = System.currentTimeMillis() - totalTime;
    }

    void displayMatching(){
	for (int i=0;i<n;i++){
	    int j = rank[i][solver.getVar(agent[i]).getVal()];
	    if (i<j) System.out.print("("+ (i+1) +","+ (j+1) +") ");
	}
	System.out.println();
    }

    void displayPhase1Table(){
	for (int i=0;i<n;i++){
	    IntDomainVar v = solver.getVar(agent[i]);
	    System.out.print(i+1 +": ");
	    for (int j=0;j<n;j++) if (v.getDomain().contains(j)) System.out.print(rank[i][j]+1 +" ");
	    System.out.println();
	}
    }

    void stats(){
	if (search) System.out.print("nodes: "+ solver.getNodeCount() +"  ");
	System.out.print("modelTime: "+ modelTime +"  ");
	if (search) System.out.print("solveTime: "+ solveTime +"  ");
	System.out.print("totalTime: "+ totalTime +"  ");
	System.out.print("modelSize: "+ modelSize +"  ");
	System.out.print("readTime: "+ readTime +" ");
	System.out.println();
    }

    public static void main(String[] args) throws IOException, ContradictionException {
	SR sr = new SR(args[0]);
	sr.build();
	if (args.length > 1) 
	    sr.solve(args[1]);
	else
	    sr.solve("first");
	sr.stats();
    }
}