import java.util.*;

public class MCX extends MC {
    MCX (int n,boolean[][] A,int[] degree) {
	super(n, A, degree);
    }
    void expand(ArrayList<Integer> C,ArrayList<Integer> P){
	expandWithX(C, P, new ArrayList<Integer>());
    }

    void expandWithX(ArrayList<Integer> C,ArrayList<Integer> P, ArrayList<Integer> X){
	// System.out.println(new String(new char[C.size()]).replace("\0", "") + C + " " + P + " " + X);
	if (timeLimit > 0 && System.currentTimeMillis() - cpuTime >= timeLimit) return;
	nodes++;

	// is there something in the not set...
	if (existsAllAdjacent(X,P)) return;
	ArrayList<Integer> newX = (ArrayList<Integer>) X.clone();
	for (int i=P.size()-1;i>=0;i--){
	    if (C.size() + P.size() <= maxSize) return;
	    int v = P.get(i);
	    C.add(v);
	    ArrayList<Integer> newP = new ArrayList<Integer>();
	    for (int w : P) if (A[v][w]) newP.add(w);
	    if (newP.isEmpty() && C.size() > maxSize) saveSolution(C);
	    ArrayList<Integer> newXandNv = new ArrayList<Integer>();
	    for (int x : newX)
		if (A[x][v]) newXandNv.add(x);
	    if (!newP.isEmpty()) expandWithX(C,newP, newXandNv);
	    C.remove((Integer)v);
	    P.remove((Integer)v);
	    newX.add(v);
	}
    }

    boolean allAdjacent(int v, ArrayList<Integer> S){
	for (int w : S) if (!A[v][w]) return false;
	return true;
    }

    boolean existsAllAdjacent(ArrayList<Integer> S1, ArrayList<Integer> S2){
	for (int v : S1) if (allAdjacent(v,S2)) return true;
	return false;
    }
}