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

// Задача "Мафия в городе"
// 8-ая Интернет-олимпиада сезона 2006-2007, базовый уровень
// Автор условия: Федор Царев, tsarev@rain.ifmo.ru
// Автор решения: Максим Буздалов, buzdalov@rain.ifmo.ru

// Решение с обратным порядком перебора (находит другие возможные ответы)

public class mafia_mb_reverse {
	static void myAssert(boolean expr, String message) {
		if (!expr) throw new AssertionError(message);
	}

	public static void main(String[] args) throws IOException {
		Scanner in = new Scanner(new File("mafia.in"));
	        PrintWriter out = new PrintWriter("mafia.out");		

	        int n = in.nextInt();
        	int m = in.nextInt();

		myAssert(2 <= n && n <= 18, "N is out of bounds");
		myAssert(0 <= m && m <= n * (n - 1) / 2, "M is out of bounds");

	        int[] s = new int[m], e = new int[m];
		for (int i = 0; i < m; i++) {
	            s[i] = in.nextInt() - 1;
	            e[i] = in.nextInt() - 1;
	            myAssert(0 <= s[i] && s[i] < n, "Start is out of bounds");
	            myAssert(0 <= e[i] && e[i] < n, "Finish is out of bounds");
	        }

	        int bestChoice = 100;
        	int count = 0;
	        int oneOf = -1;
		for (int t = (1 << n) - 1; t >= 0; t--) {
			if (Integer.bitCount(t) <= bestChoice) {
	        		boolean covers = true;
        			for (int i = 0; covers && i < m; i++) {
        				covers = ((1 << s[i]) & t) != 0 || ((1 << e[i]) & t) != 0;
        			}
				if (covers && Integer.bitCount(t) < bestChoice) {
					bestChoice = Integer.bitCount(t);
					oneOf = t;
					count = 0;
	        		}
				if (covers && Integer.bitCount(t) == bestChoice) {
					count++;		
        			}
	  	        }	
        	}

		out.println(bestChoice + " " + count);
		for (int i = 0; i < 18; i++) {
			if (((1 << i) & oneOf) != 0) {
				out.print(i + 1);
				out.print(" ");
 		        }
	        }
        	out.println();

	        out.close();
        	in.close();
	}
}
