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

public class MaxCliqueBB {
    private int[] degree;
    private int[][] A;          // adjacency matrix
    private int n,m;            // n vertices, m edges
    private long nodes;
    private int[] solution;
    private int maxSize;
    private boolean trace;
    private BitSet[] N;         // neighbourhood
    private BitSet[] notN;      // not the neighbourhood
    private Vertex[] V;         // vertices sorted by degree
    private int maxColVert;     // vertex of maximum colour, byproduct of BBCol

    public MaxCliqueBB (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];
	notN       = 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);
	    N[i] = new BitSet(n);
	    notN[i] = new BitSet(n);
	}
	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();
	for (int i=0;i<n;i++) V[i] = new Vertex(i,degree[i]);
	renameVertices();
	nodes = maxSize = 0;
	trace = false;
	maxColVert = -1;
    }

    private void renameVertices(){
	Arrays.sort(V); // in decreasing degree order
	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);
		notN[i].set(j,A[u][v] == 0);
	    }
    }

    public long getNodes(){return nodes;}
    public int  getMaxSize(){return maxSize;}
    public void setTrace(){trace = true;}

    public void search(){
	nodes = 0;
	BitSet C = new BitSet(n);
	BitSet P = new BitSet(n);
	P.set(0,n,true);
	greedyBuild(C,P); // has a small effect
	maxClique(C,P);
    }

    private void maxClique(BitSet C,BitSet P){
	nodes++;
	if (C.cardinality() + BBColour(C,(BitSet)P.clone()) <= maxSize) return;
	int v = maxColVert;
	BitSet C_new = (BitSet)C.clone(); 
	BitSet P_new = (BitSet)P.clone();
	if (select(v,C_new,P_new)) maxClique(C_new,P_new);
	if (reject(v,C,P)) maxClique(C,P);
    }

    private boolean select(int v,BitSet C,BitSet P){
	C.set(v,true);
	P.and(N[v]);
	if (C.cardinality() > maxSize) saveSolution(C);
	if (C.cardinality() + P.cardinality() <= maxSize) return false;
	return true;
    }

    private boolean reject(int v,BitSet C,BitSet P){
	P.set(v,false);
	if (C.cardinality() + P.cardinality() <= maxSize) return false;
	return true;
    }
   
    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 void greedyBuild(BitSet C,BitSet P){
	BitSet C_new = new BitSet(n);
	BitSet P_new = (BitSet)P.clone();
	while (P_new.cardinality() > 0) select(chooseMaxDegree(P_new),C_new,P_new);
	saveSolution(C_new);
	for (int i = P.nextSetBit(0);i >= 0;i = P.nextSetBit(i+1)){
		degree[i] = getDegree(i,P);
		if (degree[i] < maxSize) P.set(i,false);
	}
    }

    private int BBColour(BitSet C,BitSet P){
	int colour = 0;
	maxColVert = -1;
       	while (P.cardinality() != 0){
	    BitSet Q = (BitSet)P.clone();
	    while (Q.cardinality() != 0){
		int v = chooseMaxDegree(Q);
		P.set(v,false);
		Q.set(v,false);
		Q.and(notN[v]);
		maxColVert = v;
	    }
	    colour++;
	}
	return colour;
    }	    

    private void saveSolution(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");
	    return;
	}
	String fname = args[0];
	MaxCliqueBB mc = new MaxCliqueBB(fname);
	if (args.length > 1) mc.setTrace();
	long cpuTime = System.currentTimeMillis();
	mc.search();
	cpuTime = System.currentTimeMillis() - cpuTime;
	System.out.println(mc.getMaxSize() +" "+ mc.getNodes() +" "+ cpuTime +" ");
	System.out.println(mc.getSolution());
    }
}