//
// explores colour classes newest first
// within colour class, oldest vertex first
//
import java.util.*;

class MCX extends MCQ {

    MCX (int n,int[][]A,int[] degree,int style) {
	super(n,A,degree,style);
    }

    void search(){
	cpuTime                                    = System.currentTimeMillis();
	nodes                                      = 0;
	ArrayList<Integer> C                       = new ArrayList<Integer>(n);
	ArrayList<Integer> P                       = new ArrayList<Integer>(n);
	orderVertices(P);
	expand(C,P);
    }

     void expand(ArrayList<Integer> C,ArrayList<Integer> P){
	if (timeLimit > 0 && System.currentTimeMillis() - cpuTime >= timeLimit) return;
	nodes++;	
	ArrayList<ArrayList<Integer>> colourClasses = colourSort(C,P);
	int m = colourClasses.size();
	for (int i=0;m + C.size() > maxSize;i++){
	    ArrayList<Integer> colourClass = colourClasses.get(i);
	    for (int j=0;j<colourClass.size();j++) P.remove((Integer)colourClass.get(j));
	    for (int j=0;j<colourClass.size();j++){
		int v = colourClass.get(j);
		C.add(v);
		ArrayList<Integer> newP = new ArrayList<Integer>();
		for (int k=0;k<P.size();k++){
		    int w = P.get(k);
		    if (adjacent(v,w)) newP.add(w);
		}
		if (newP.isEmpty() && C.size() > maxSize) saveSolution(C);
		if (!newP.isEmpty()) expand(C,newP);
		C.remove((Integer) v);
	    }
	    m--;
	}
    }

    ArrayList<ArrayList<Integer>> colourSort(ArrayList<Integer> C,ArrayList<Integer> colOrd){
	int m = colOrd.size();
	ArrayList<Integer> P = new ArrayList<Integer>(m);
	ArrayList<ArrayList<Integer>> colourClasses = new ArrayList<ArrayList<Integer>>();
	for (int i=0;i<colOrd.size();i++) P.add(colOrd.get(i));
	while (!P.isEmpty()){
	    ArrayList<Integer> colourClass = new ArrayList<Integer>();
	    for (int i=0;i<P.size();i++){
		int v = P.get(i);
		if (!conflicts(v,colourClass)) colourClass.add(v);
	    }
	    colourClasses.add(colourClass);
	    for (int i=0;i<colourClass.size();i++) P.remove((Integer)colourClass.get(i));
	}
	return colourClasses;
    }
}