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

public class BBMC {
    private int[] degree;
    private int[][] A;          // adjacency matrix
    private int n,m;            // n vertices, m edges
    private long timeLimit;     // seconds
    private long cpuTime;       // milliseconds
    private long nodes;
    private int[] solution;
    private int maxSize;
    private int style;          // style of static ordering
    private boolean trace;
    private BitSet[] N;         // neighbourhood
    private BitSet[] invN;      // not the neighbourhood
    private Vertex[] V;         // vertices sorted by degree

    public BBMC (String fname) throws IOException {
	String b     = "";
	Scanner sc   = new Scanner(new File(fname));
	while (sc.hasNext() && !b.equals("p")) b = sc.next();
	sc.next();
	n          = sc.nextInt();          // # vertices
	m          = sc.nextInt();          // # edges
	degree     = new int[n];
	A          = new int[n][n];
	N          = new BitSet[n];
	invN       = new BitSet[n];
	solution   = new int[n];
	V          = new Vertex[n];
	for (int i=0;i<n;i++){	    
	    degree[i] = 0;
	    Arrays.fill(A[i],0);
	}
	while (sc.hasNext()){
	    b     = sc.next(); // skip "edge"
	    int i = sc.nextInt() - 1;
	    int j = sc.nextInt() - 1; 
	    degree[i]++; degree[j]++;
	    A[i][j] = A[j][i] = 1;
	}
	sc.close();
	nodes = maxSize = 0;
	timeLimit = -1;
	cpuTime = -1;
	style = 1;
	trace = false;
    }

    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 long getNodes(){return nodes;}
    public int  getMaxSize(){return maxSize;}
    public void setTrace(){trace = true;}
    public void setTimeLimit(long seconds){timeLimit = seconds;}
    public void setStyle(int style){this.style = style;}
    
    public void search(){
	nodes    = 0;
	cpuTime  = System.currentTimeMillis();
	for (int i=0;i<n;i++){	  
	    N[i]    = new BitSet(n);
	    invN[i] = new BitSet(n);
	    V[i]    = new Vertex(i,degree[i]);
	}
	renameVertices();
	BitSet C = new BitSet(n);
	BitSet P = new BitSet(n);
	C.set(0,n,false);
	P.set(0,n,true);
	BBMaxClique(C,P);
    }
    
    private void BBMaxClique(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);
	for (int i=m-1;i>=0;i--){
	    if (colour[i] + C.cardinality() <= maxSize) return;
	    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()) BBMaxClique(C,P_new);
	    P.set(v,false); C.set(v,false);
	}
    }

     private void BBColour(BitSet C,BitSet P,int[] U,int[] colour){
	int colourClass = 0;
	int i = 0;
       	while (P.cardinality() != 0){
	    colourClass++;
	    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++] = colourClass; // and its respective colour
	    }
	}
    }

    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 String getSolution(){
	String s = "";
	for (int i=0;i<n;i++)
	    if (solution[i] == 1) s = s + i + " ";
	return s;
    }
    
    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());
    }
}