//
// visit colour classes in increasing size order, tie breaking on age 
// visit vertices in colour class, oldest first
//

import java.util.*;

class MCV extends MCQ {

    Stack[] colourClassStack;

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

    void search(){
	cpuTime                                    = System.currentTimeMillis();
	nodes                                      = 0;
	colourClassStack                           = new Stack[n+1];
	ArrayList<Integer> C                       = new ArrayList<Integer>(n);
	ArrayList<Integer> P                       = new ArrayList<Integer>(n);
	for (int i=0;i<=n;i++) colourClassStack[i] = new Stack();
	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();
	int minSize = m;
	int maxSize = 0;
	int size = 0;
	ArrayList<Integer> P = new ArrayList<Integer>(m);
	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);
	    }
	    size = colourClass.size();
	    minSize = Math.min(minSize,size);
	    maxSize = Math.max(maxSize,size);
	    colourClassStack[size].push(colourClass);
	    for (int i=0;i<size;i++) P.remove((Integer)colourClass.get(i));
	}
	ArrayList<ArrayList<Integer>> colourClasses = new ArrayList<ArrayList<Integer>>();
	for (int i=minSize;i<=maxSize;i++) 
	    while (!colourClassStack[i].isEmpty()) colourClasses.add((ArrayList<Integer>)colourClassStack[i].pop());
	return colourClasses;
    }
}