import java.io.*;
import java.util.*;
import org.chocosolver.solver.Model;
import org.chocosolver.solver.Solver;
import org.chocosolver.solver.variables.IntVar;
import org.chocosolver.solver.search.strategy.Search;


public class VertexCover {

  
    public static void main(String[] args) throws IOException {
	Scanner sc     = new Scanner(new File(args[0]));

	sc.next(); sc.next(); // p td
	
	int n          = sc.nextInt(); // vertices
	int m          = sc.nextInt(); // edges
	Model model    = new Model(args[0]);
	Solver solver  = model.getSolver();
	IntVar[] v     = model.intVarArray("v",n,0,1); // n variables
	IntVar total   = model.intVar("total",0,n); // number of vertices selected
	int[] selected = new int[n];
	int nSelected  = 0;

	while (sc.hasNext()){
	    int i = sc.nextInt() - 1;
	    int j = sc.nextInt() - 1;
	    model.arithm(v[i],"+",v[j],">",0).post(); // select a vertex from the edge
	}
	sc.close();

	model.sum(v,"=",total).post();

	model.setObjective(Model.MINIMIZE,total);
	solver.setSearch(Search.minDomLBSearch(v));
	if (args.length > 1) solver.showDecisions();
	solver.limitTime(1000000);

	while (solver.solve()){
	    nSelected = total.getValue();
	    for (int i=0;i<n;i++) selected[i] = v[i].getValue();
	}

	System.out.println("selected: "+ nSelected);
	//for (int i=0;i<n;i++) System.out.print(selected[i]);
	//System.out.println();
	System.out.println("nodes: " + solver.getMeasures().getNodeCount() + 
                           "   cpu: " + solver.getMeasures().getTimeCount());
    }
}