import java.util.*;
import java.io.*;

public class MaxCliquePP extends MaxClique {
    private MySet V;                   // set of vertices
    private ArrayStack<Integer> DeleteStack;     // used throughout
    private ArrayList<Integer> L;      // used throughout
    private Vertex[][] vertex;    
    private DegreeComparator compareDegree;
    private BitSet[] N;         // neighbourhood
    private BitSet[] invN;      // not the neighbourhood

    public MaxCliquePP (String fname) throws IOException {
	super(fname);
	V             = new MySet(n);
	vertex        = new Vertex[n][n];
	compareDegree = new DegreeComparator();
	for (int i=0;i<n;i++) V.add((Integer)i);
	DeleteStack = new ArrayStack<Integer>(n*n);
	L = new ArrayList<Integer>(n);
	for (int i=0;i<n;i++) 
	    for (int j=0;j<n;j++) vertex[i][j] = new Vertex(j,degree[j]);
	N    = new BitSet[n];
	invN = new BitSet[n];
	for (int i=0;i<n;i++){	  
	    N[i]    = new BitSet(n);
	    invN[i] = new BitSet(n);
	    for (int j=0;j<n;j++){
		N[i].set(j,A[i][j] == 1);
		invN[i].set(j,A[i][j] == 0);
	    }
	}
    }

    public void search(){
	nodes   = 0;
	cpuTime = System.currentTimeMillis();
	maxClique(0,new MySet(n),V);
    }

    private void maxClique(int depth,MySet C,MySet P){
	if (timeLimit > 0 && (System.currentTimeMillis() - cpuTime)/1000 >= timeLimit) return;
	nodes++;
	Vertex[] sortedVertex = new Vertex[P.size()];
	int k = 0;
	for (int u : P) sortedVertex[k++] = vertex[depth][u];
	Arrays.sort(sortedVertex,compareDegree);
	Stack<Vertex> S = numberSort(sortedVertex);
	//Stack<Vertex> S = BBColour(sortedVertex);
	while (!S.isEmpty()){
	    Vertex v = S.pop();
	    if (C.size() + v.getColour() <= maxSize) return;
	    for (int u : P) vertex[depth+1][u].setDegree(vertex[depth][u].getDegree());
	    P.push(); C.push();
	    if (select(depth+1,v.getIndex(),C,P)) maxClique(depth+1,C,P);
	    P.pop(); C.pop();
	    reject(depth,v.getIndex(),C,P);
	}
    }
    //
    // NOTE 1: it is possible that a vertex can be on the stack but has been deleted from P
    //         this happens due to aggressive filtering in reject(...) removing vertices
    //         of low degree as vertices are removed and maxSize (globally) increases as search
    //         proceeds. Therefore redundant calls could be cut! However, so far any vertex
    //         that satisfies this condition appears to be rejected because its colour is too low
    //  

    private boolean select(int depth,int v,MySet C,MySet P){
	C.add((Integer)v);
	if (C.size() > maxSize) saveSolution(C);
	DeleteStack.clear();
	for (int i=0;i<P.size();i++){
	    int u = P.getNth(i);
	    if (A[u][v] == 0) DeleteStack.push(u);
	} // get all vertices in P not adjacent to v
	int delta = maxSize - C.size() + 1;
	return remove(depth,P,delta);
    }

    private boolean reject(int depth,int v,MySet C,MySet P){
	int delta = maxSize - C.size() + 1;
	DeleteStack.clear();
	DeleteStack.push(v);
	return remove(depth,P,delta);
    }

    private boolean remove(int depth,MySet P,int delta){
	while (!DeleteStack.isEmpty()){
	    int u = DeleteStack.pop();
	    if (P.contains(u)){
		P.remove((Integer)u);
		if (P.size() < delta) return false;
		for (int i=0;i<P.size();i++){
		    int w = P.getNth(i);
		    if (A[u][w] == 1){
			vertex[depth][w].decrementDegree();
			if (vertex[depth][w].getDegree() + 1 < delta) DeleteStack.push(w); // LESS NODES MORE TIME
		    }
		}
	    }
	}
	return !P.isEmpty();
    }
    //
    // removes all vertices on the DeleteStack from P
    //

    private Stack<Vertex> numberSort(Vertex[] v_in){
	int colours = 0;
	int m = v_in.length;
	ArrayList[] colourClass = new ArrayList[m];
	for (Vertex v : v_in){
	    int k = 0;
	    while (colourClass[k] != null && conflicts(v,colourClass[k])) k++;
	    if (colourClass[k] == null) colourClass[k] = new ArrayList<Vertex>(m);
	    colourClass[k].add(v);
	    v.setColour(k+1);
	    colours = Math.max(colours,k+1);
	}
	Stack<Vertex> S = new Stack<Vertex>();
	for (int k=0;k<colours;k++)
	    for (Vertex v : (ArrayList<Vertex>)colourClass[k]) S.push(v);
	return S;
    }

    private Stack<Vertex> BBColour(Vertex[] v_in){
	BitSet P = new BitSet(n);
	for (Vertex v : v_in){P.set(v.getIndex(),true); v.setFlag(true);}
	Stack<Vertex> S = new Stack<Vertex>();
	int maxColour = 0;
       	while (P.cardinality() != 0){
	    maxColour++;
	    BitSet Q = (BitSet)P.clone();
	    while (Q.cardinality() != 0){
		Vertex w = null;
		for (Vertex v : v_in) if (v.getFlag()){w = v; break;}
		P.set(w.getIndex(),false);
		Q.set(w.getIndex(),false);
		Q.and(invN[w.getIndex()]);
		S.push(w);
		w.setColour(maxColour);
		w.setFlag(false);
	    }
	}
	return S;
    }

    private boolean conflicts(Vertex v,ArrayList<Vertex> V){
	for (Vertex u : V) if (A[u.getIndex()][v.getIndex()] == 1) return true;
	return false;
    }

    private void saveSolution(MySet C){
	for (int i=0;i<n;i++) 
	    if (C.contains((Integer)i))
		solution[i] = 1;
	    else
		solution[i] = 0;
	maxSize = C.size();
    }

     public static void main(String[] args)  throws IOException {
	if (args.length == 0){
	    System.out.println("fname cpuLimit style trace");
	    return;
	}
	String fname   = args[0];
	MaxCliquePP mc = new MaxCliquePP(fname);
	if (args.length > 1) mc.setTimeLimit((long)Integer.parseInt(args[1]));
	if (args.length > 2) mc.setStyle(Integer.parseInt(args[2]));
	//if (args.length > 3) mc.setTrace();
	long cpuTime = System.currentTimeMillis();
	mc.search();
	cpuTime = System.currentTimeMillis() - cpuTime;
	System.out.println(mc.getMaxSize() +" "+ mc.getNodes() +" "+ cpuTime +" true");
	System.out.println(mc.getSolution());
    }
}