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

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

    private static String getSolution(){
	String s = "";
	for (int i=0;i<n;i++)
	    if (solution[i] == 1) s = s + i + " ";
	return s;
    }

private static void BBMaxClique(BitSet C,BitSet P){
 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 static 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;    
     colour[i++] = colourClass;
    }
  }
}

private static void search(){
 nodes = 0;
 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 static void renameVertices(){
  if (style == 1) Arrays.sort(V,new DegreeComparator());
  if (style == 2) minWidthOrder();
  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);
    }
}

private static 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 static boolean isAdjacent(Vertex v,Vertex u){
  return A[v.getIndex()][u.getIndex()] == 1;
}

private static 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 {
	String b     = "";
	Scanner sc   = new Scanner(new File(args[0]));
	while (sc.hasNext() && !b.equals("p")) b = sc.next();
	sc.next();
	n          = sc.nextInt();  
	m          = sc.nextInt();  
	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];
	Arrays.fill(degree,0);
	for (int i=0;i<n;i++) 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;
	style = 1;
	if (args.length > 1) style = Integer.parseInt(args[1]);
	long cpuTime = System.currentTimeMillis();
	search();
	cpuTime = System.currentTimeMillis() - cpuTime;
	System.out.println(maxSize +" "+ nodes +" "+ cpuTime);
	System.out.println(getSolution());
    }
}