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

public class SIP0 {

    long nodes;              // number of decisions
    long timeLimit;          // milliseconds
    long cpuTime;            // milliseconds
    int[] solution;          // as it says
    boolean matched;         // is there a matching?
    boolean trace;           // trace, anyone for trace?
    boolean timeout;         // true if timed out
    boolean firstSolution;   // only wanting 1st solution?
    boolean verbose;         // want solution displayed?
    boolean induced;         // induced or (default) partial?
    int solutions;           // number of solutions found
    int fails;               // something like a failed node
    Graph P;                 // the pattern graph
    Graph T;                 // the target graph

    SIP0 (String fnameP,String fnameT) throws IOException {
	P = new Graph(fnameP);
	T = new Graph(fnameT);
	nodes = cpuTime = solutions = fails = 0;
	matched = trace = timeout = firstSolution = verbose = induced = false;
	solution = new int[P.n];
    }

    Variable select(Variable[] U){
	int smallest = 0;
	for (int i=1;i<U.length;i++)
	    if (U[i].domain.cardinality() < U[smallest].domain.cardinality()) smallest = i;
	return U[smallest];
    }
    //
    // select the first variable with smallest doamin
    //

    boolean compatible(ArrayList<Integer> uLabel,ArrayList<Integer> vLabel){
	if (uLabel.size() > vLabel.size()) return false;
	for (int i=0;i<uLabel.size();i++)
	    if (uLabel.get(i) > vLabel.get(i)) return false;
	return true;
    }
    //
    // a vertex in the pattern graph with the label uLabel
    // is compatible with a vertex in the target graph with vLabel
    // if uLabel is subsumed by vLabel, where a label is neighbourhood degree sequence
    //

    void solve(){
	cpuTime  = System.currentTimeMillis();
	Variable[] U = new Variable[P.n];
	for (int i=0;i<P.n;i++){
	    BitSet domain = new BitSet(T.n);
	    for (int j=0;j<T.n;j++)
		domain.set(j,compatible(P.label[i],T.label[j]));
	    U[i] = new Variable(i,domain);
	}		
	Arrays.sort(U);
	try{expand(U);} catch(TimeOutException e){timeout = true;}
    }

    boolean expand(Variable[] U){	
	if (timeLimit > 0 && System.currentTimeMillis() - cpuTime >= timeLimit) throw new TimeOutException();
	int n = U.length;
	if (n == 0){solutions++; if (verbose) display(); return firstSolution;}
	nodes++;
	Variable[] newU = new Variable[n-1];
	Variable u = select(U);
	boolean consistent = false;
	for (int i = u.domain.nextSetBit(0);i>=0 && !consistent;i=u.domain.nextSetBit(i+1)){
	    consistent = true;
	    solution[u.index] = i;
	    for (int j=0,k=0;j<n && consistent;j++){
		Variable v = U[j];
		if (u.index != v.index){
		    Variable newV = new Variable(v.index,(BitSet)v.domain.clone());
		    newV.domain.set(i,false);
		    if (P.adjacent(u.index,v.index)) newV.domain.and(T.N[i]);
		    else if (induced) newV.domain.and(T.notN[i]);
		    newU[k++] = newV;
		    consistent = !newV.domain.isEmpty();
		}
		if (!consistent) fails++;
	    }
	    consistent = consistent && expand(newU);
	}
	return consistent;
    }
    //
    // simple forward checking
    //

    void display(){
	System.out.print("Solution "+ solutions +":");
	for (int i=0;i<P.n;i++) System.out.print(" "+ i +"="+ solution[i]);	
	System.out.println();
    }
}