//
// Minimize Blocking Pairs in SR (and SM) with Forbidden edges
//
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.*;

public class MinBPSRForbidden {	
   
    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]
    int[] length; // length of agent's preference list
    boolean[][] forbidden; // forbidden[i][j] <-> forbidden matching between agents i and j
    Model model;
    Solver solver;
    IntegerVariable[] agent; // domain of preferences, last is unmatched
    IntegerVariable[][] conflict; // conflict[i][j] = 0  <-> stable(i,j)
    IntegerVariable[] flatConflict; // flattened version of conflict, to minimise sum
    IntegerVariable totalConflicts; // sum of flatConflict
    long totalTime, modelTime, solveTime, readTime, modelSize;
    int size; // size of matching
    boolean search;

    MinBPSRForbidden(String fname) throws IOException {
	search      = true;
	totalTime   = System.currentTimeMillis();
	readTime    = System.currentTimeMillis();
	read(fname);
	readTime = System.currentTimeMillis() - readTime; 
    }

    void read(String fname) throws IOException {
	BufferedReader fin = new BufferedReader(new FileReader(fname));
	n                  = Integer.parseInt(fin.readLine());
	pref               = new int[n][n]; 
	rank               = new int[n][n]; 
	length             = new int[n];
	forbidden          = new boolean[n][n];
	for (int i=0;i<n;i++){
	    StringTokenizer st = new StringTokenizer(fin.readLine()," ");
	    int k = 0;
	    length[i] = 0;
	    while (st.hasMoreTokens()){
		int j      = Integer.parseInt(st.nextToken()) - 1;
		rank[i][j] = k;
		pref[i][k] = j;
		length[i]  = length[i] + 1;
		k          = k + 1;
	    }
	    rank[i][i] = k;
	    pref[i][k] = i;
	}
	String buffer = fin.readLine();
	while (buffer != null){
	    StringTokenizer st = new StringTokenizer(buffer);
	    String s = st.nextToken();
	    int u = Integer.parseInt(st.nextToken()) - 1;
	    int v = Integer.parseInt(st.nextToken()) - 1;
	    forbidden[u][v] = forbidden[v][u] = true;
	    buffer = fin.readLine();
	}
	fin.close();
    }	

    void build(){
	modelTime      = System.currentTimeMillis();
	model          = new CPModel(); 
	agent          = new IntegerVariable[n]; // domain of preferences, last is unmatched
	conflict       = new IntegerVariable[n][n];
	flatConflict   = new IntegerVariable[n*(n-1)/2];
	totalConflicts = makeIntVar("totalConflicts",0,n*(n-1)/2);
	for (int i=0;i<n;i++) agent[i] = makeIntVar("agent_"+ i,0,length[i],"cp:enum");
	model.addVariables(agent);
	for (int i=0;i<n-1;i++)
	    for (int j=i+1;j<n;j++)
		conflict[i][j] = conflict[j][i] = makeIntVar("conf_" + i +"_"+ j,0,1);
	for (int i=0;i<n;i++)
	    for (int j=0;j<length[i];j++){
		int k = pref[i][j]; // k is the agent in position j of i's preference list
		model.addConstraint(ifOnlyIf(eq(conflict[i][k],0),implies(gt(agent[i],rank[i][k]),lt(agent[k],rank[k][i]))));
		model.addConstraint(implies(eq(agent[i],rank[i][k]),eq(agent[k],rank[k][i])));
	    }
	for (int i=0,count=0;i<n-1;i++)
	    for (int j=i+1;j<n;j++,count++){
		if (forbidden[i][j]){
		    model.addConstraint(neq(agent[i],rank[i][j]));
		    model.addConstraint(neq(agent[j],rank[j][i]));
		}
		flatConflict[count] = conflict[i][j];
	    }
	model.addConstraint(eq(totalConflicts,sum(flatConflict)));
	solver     = new CPSolver(); 
	solver.read(model); 
	modelTime  = System.currentTimeMillis() - modelTime;
	modelSize  = (Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory())/1024; // kilobytes
    }

    void minimize(String command) throws ContradictionException {
	solveTime = System.currentTimeMillis();
	//solver.setVarIntSelector(new MinDomain(solver,solver.getVar(agent)));
	//solver.setVarIntSelector(new MinDomain(solver,solver.getVar(flatConflict)));
	if (command.equals("propagate")){
	    search = false;
	    try{solver.propagate(); displayPhase1Table();} catch (ContradictionException e){displayPhase1Table();}
	}
	else if (command.equals("maximize") && solver.maximize(solver.getVar(totalConflicts),true).booleanValue()) displayMatching();
	else if (solver.minimize(solver.getVar(totalConflicts),true).booleanValue()) displayMatching();
	solveTime = System.currentTimeMillis() - solveTime;
	totalTime = System.currentTimeMillis() - totalTime;
    }

    void displayMatching(){
	for (int i=0;i<n;i++){
	    int j = pref[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("conflicts: "+ solver.getVar(totalConflicts).getVal() +"  ");
	}
	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 +" ");
	size = 0;
	for (int i=0;i<n;i++){
	    int j = pref[i][solver.getVar(agent[i]).getVal()];
	    if (i<j) size++;
	}
	System.out.print("size: "+ size +" ");
	System.out.println();
    }

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