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

public class MaxCliqueBB extends MaxClique {

    private BitSet[] N;         // neighbourhood
    private BitSet[] invN;      // not the neighbourhood
    private Vertex[] V;         // vertices sorted by degree

    public MaxCliqueBB (String fname) throws IOException {
	super(fname);
	N          = new BitSet[n];
	invN       = new BitSet[n];
	V          = new Vertex[n];
    }

    private void init(){
	for (int i=0;i<n;i++){	  
	    N[i]    = new BitSet(n);
	    invN[i] = new BitSet(n);
	    V[i]    = new Vertex(i,degree[i]);
	}
    }

    private void minWidthOrder(){
	ArrayList<Vertex> L = new ArrayList<Vertex>(n);
	Stack<Vertex> S     = new Stack<Vertex>();
	for (Vertex v : V) L.add(v);
	while (!L.isEmpty()){
	    Vertex v = L.get(0);
	    for (Vertex u : L) if (u.getDegree() < v.getDegree()) v = u;
	    S.push(v); L.remove(v);
	    for (Vertex u : L) if (isAdjacent(u,v)) u.decrementDegree();
	}
	int k=0;
	while (!S.isEmpty()) V[k++] = S.pop();
    }

    private boolean isAdjacent(Vertex v,Vertex u){return A[v.getIndex()][u.getIndex()] == 1;}

    private void swap(Vertex[] V,int i, int j){
	Vertex temp = V[i];
	V[i] = V[j];
	V[j] = temp;
    }

    private void minWidthOrder1(){
	for (int i=n-1;i>0;i--){
	    for (int j=0;j<i;j++) 
		if (V[j].getDegree() < V[i].getDegree()) swap(V,i,j);
	    for (int j=0;j<i;j++) 
		if (isAdjacent(V[i],V[j])) V[j].decrementDegree();
	}
    }
	

    private void brelazOrder(){
	ArrayList<Vertex> L = new ArrayList<Vertex>(n);
	ArrayList<Vertex> ordered = new ArrayList<Vertex>(n);
	for (Vertex v : V){v.init(n); L.add(v);}
	while (!L.isEmpty()){
	    Vertex v = selectMaxSaturatedUncolouredVertex(L);
	    colourVertex(v);
	    L.remove(v);
	    ordered.add(v);
	}
	int k=0;
	for (Vertex v : ordered){V[k] = v; k++;};
    }

    private Vertex selectMaxSaturatedUncolouredVertex(ArrayList<Vertex> L){
	Vertex v = L.get(0);
	for (Vertex w : L)
	    if (w.getSaturation() > v.getSaturation() ||
		w.getSaturation() == v.getSaturation() && w.getDegree() > v.getDegree())
		v = w;
	return v;
    }

    private void colourVertex(Vertex v){
	int i   = v.getIndex();
	int col = v.colour();
	for (int j=0;j<n;j++)
	    if (A[i][j] == 1 && V[j].hasColour(col)){
		V[j].removeColour(col);
		V[j].incrementSaturation();
	    }
    }

    private void renameVertices(){
        if (style == 1) Arrays.sort(V,new DegreeComparator()); // degree order
	if (style == 2) minWidthOrder();                       // min width (smallest-last) order
	if (style == 3) brelazOrder();                         // brelaz order
	if (style == 4) {                                      // saturation order
	    brelazOrder();
	    Arrays.sort(V,new SaturationComparator()); 
	}
	if (trace) for (Vertex v : V) System.out.println(v);
	for (int i=0;i<n;i++)
	    for (int j=0;j<n;j++){
		int u = V[i].getIndex();
		int v = V[j].getIndex();
		N[i].set(j,A[u][v] == 1);
		invN[i].set(j,A[u][v] == 0);
	    }
    }
    
    public void search(){
	nodes   = 0;
	cpuTime = System.currentTimeMillis();
	init();
	renameVertices();
	BitSet C = new BitSet(n);
	BitSet P = new BitSet(n);
	C.set(0,n,false);
	P.set(0,n,true);
	maxClique(C,P);
    }
    
    private void maxClique(BitSet C,BitSet P){
	if (timeLimit > 0 && (System.currentTimeMillis() - cpuTime)/1000 >= timeLimit) return;
	nodes++;
	int m = P.cardinality();
	int[] U   = new int[m];
	int[] colour = new int[m];
	BBColour(C,(BitSet)P.clone(),U,colour);
	//numberSort(C,(BitSet)P.clone(),U,colour);
	for (int i=m-1;i>=0 && colour[i] + C.cardinality() > maxSize;i--){
	    BitSet P_new = (BitSet)P.clone();	    
	    int v = U[i];
	    C.set(v,true); P_new.and(N[v]);
	    if (P_new.isEmpty() && C.cardinality() > maxSize) save(C);
	    if (!P_new.isEmpty()) maxClique(C,P_new);
	    P.set(v,false); C.set(v,false);
	}
    }

     private void BBColour(BitSet C,BitSet P,int[] U,int[] colour){
	int maxColour = 0;
	int i = 0;
       	while (P.cardinality() != 0){
	    maxColour++;
	    BitSet Q = (BitSet)P.clone();
	    while (Q.cardinality() != 0){
		int v = chooseMaxDegree(Q);
		P.set(v,false);
		Q.set(v,false);
		Q.and(invN[v]);
		U[i] = v;        // add vertices to U in colour class order
		colour[i++] = maxColour; // and its respective colour
	    }
	}
    }
    
    private int chooseMaxDegree(BitSet P){return P.nextSetBit(0);}
    
    private int chooseMinDegree(BitSet P){
	for (int i=n-1;i>=0;i--) if (P.get(i)) return i;
	return -1;
    }
    
    private int getDegree(int v,BitSet P){ // get active degree of vertex v in P
	BitSet P_new = (BitSet)P.clone();
	P_new.and(N[v]);
	return P_new.cardinality();
    }
    
    private boolean compatible1(BitSet C,int v){
	BitSet C_clone = (BitSet)C.clone();
	C_clone.and(N[v]);
	return C_clone.isEmpty();
    }


    private boolean compatible(BitSet C,int v){
	for (int w = C.nextSetBit(0);w>=0;w=C.nextSetBit(w+1))
	    if (N[v].get(w)) return false;
	return true;
    }

    private int numberSort(BitSet C,BitSet P,int[] U,int[] Col){
	int colours = 0;
	BitSet [] ColourClass = new BitSet[P.cardinality()];
	for (int v = P.nextSetBit(0);v >= 0;v = P.nextSetBit(v+1)){
	    int k = 0;
	    while (ColourClass[k] != null && !compatible(ColourClass[k],v)) k++;
	    if (ColourClass[k] == null) ColourClass[k] = new BitSet(P.cardinality());
	    ColourClass[k].set(v,true);
	    colours = Math.max(colours,k+1);
	}
	int i=0;
	for (int k=0;k<colours;k++){
	    for (int j = ColourClass[k].nextSetBit(0);j >= 0;j = ColourClass[k].nextSetBit(j+1)){
		U[i] = j;
		Col[i] = k+1;
		i++;
	    }
	}
	return colours;
    }
    //
    // Tomita & Seki DMTCS 2003
    //	    
    
    private void save(BitSet C){
	Arrays.fill(solution,0);
	for (int i=0;i<n;i++) if (C.get(i)) solution[V[i].getIndex()] = 1;
	maxSize = C.cardinality();
    }
    
    public static void main(String[] args)  throws IOException {
	if (args.length == 0){
	    System.out.println("fname cpuLimit style trace");
	    return;
	}
	String fname   = args[0];
	MaxCliqueBB mc = new MaxCliqueBB(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());
    }
}