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

public class BBMC extends MaxClique {
    private BitSet[] N;         // neighbourhood
    private BitSet[] invN;      // not the neighbourhood
    private Vertex[] V;         // vertices sorted by degree

    public BBMC (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 renameVertices(){
        if (style == 1) Arrays.sort(V,new DegreeComparator()); // degree order
	if (style == 2) minWidthOrder();                       // min width (smallest-last) order
	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 = Q.nextSetBit(0);
		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 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];
	BBMC mc = new BBMC(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());
    }
}