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

class MCZ extends MCYrev {

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

     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(m-1);
	    for (int j=0;j<colourClass.size();j++) P.remove((Integer)colourClass.get(j));
	    for (int j=colourClass.size();j>0;j--){
		int v = colourClass.get(j-1);
		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);
		//P.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>>();
	ArrayList<ArrayList<Integer>> singletons    = 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);
	    }
	    if (colourClass.size() == 1) singletons.add(colourClass); else colourClasses.add(colourClass);
	    for (int i=0;i<colourClass.size();i++) P.remove((Integer)colourClass.get(i));
	}
	for (int i=0;i<singletons.size();i++) colourClasses.add(singletons.get(i));
	return colourClasses;
    }
}