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

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

public class mafia_ft implements Runnable {

	private Scanner in;
	private PrintWriter out;
	String fname = "mafia";

	int bitCount(int x) {
		int res = 0;
		while (x > 0) {
			res++;
			x &= x - 1;
		}
		return res;
	}

	public void solve() {
		int n = in.nextInt();
		int m = in.nextInt();
		int[] u = new int[m];
		int[] v = new int[m];
		for (int i = 0; i < m; i++) {
			u[i] = in.nextInt() - 1;
			v[i] = in.nextInt() - 1;
		}
		int ans1 = Integer.MAX_VALUE;
		int ans2 = 0;
		int best = -1;
		for (int mask = 0; mask < (1 << n); mask++) {
			int cur = bitCount(mask);
			boolean good = true;
			for (int i = 0; i < m; i++) {
				int cu = u[i];
				int cv = v[i];
				boolean cg = false;
				cg |= (mask & (1 << cu)) != 0;
				cg |= (mask & (1 << cv)) != 0;
				good &= cg;
				if (!good) {
					break;
				}
			}
			if (good) {
				if (cur < ans1) {
					ans1 = cur;
					ans2 = 0;
					best = mask;
				}
				if (cur == ans1) {
					ans2++;
				} 
			}
		}

		out.println(ans1 + " " + ans2);
		for (int i = 0; i < n; i++) {
			if ((best & (1 << i)) != 0) {
				out.print((i + 1) + " ");
			}
		}
		out.println();
	}

	public void run() {
		try {
			solve();
		} catch (Exception e) {
			e.printStackTrace();
			System.exit(1);
		} finally {
			out.close();
		}		
	}

	public mafia_ft() {
		try {
			in = new Scanner(new File(fname + ".in"));
			out = new PrintWriter(new File(fname + ".out"));
		} catch (Exception e) {
			e.printStackTrace();
			System.exit(1);
		}
	}


	public static void main(String[] args) {
		new Thread(new mafia_ft()).start();
	}

}