Об этом ещё никто не знает, но многие догадываются - мафия уже в городе. Поговаривают, что в планах главы мафиозного клана захват контроля над всем городом, однако поначалу он решил ограничиться захватом основных линий связи города.
В городе находятся n базовых телефонных станций, некоторые пары которых соединены двустронними каналами связи. Для удобства, занумеруем базовые станции целыми числами от 1 до n, канал связи в этом случае задается парой чисел (u, v) - номерами станций, которые он соединяет.
Будем говорить, что канал связи (u, v) контролируется мафией, если захвачена либо станция u, либо станция v (либо обе).
Глава мафиозного клана хочет контролировать все каналы связи, захватив при этом как можно меньше базовых станций. Ваша задача - помочь службе безопасности телефонной компании, составив возможный план захвата и определив количество таких планов.
Первая строка входного файла содержит два целых числа: n и m (2 ≤ n ≤ 18, 0 ≤ m). Каждая из последующих m строк описывает один канал связи и содержит по два целых числа: u и v (1 ≤ u, v ≤ n, u ≠ v) - номера базовых станций, соединённых этим каналом связи. Любая пара станций соединена не более чем одним каналом.
В первой строке выходного файла выведите два числа: k и c - соответственно, минимальное количество базовых станций, которые необходимо захватить для того, чтобы контролировать все каналы связи, и число способов захватить такое количество станций, так чтобы контролировать все каналы связи.
Во второй строке выходного файла выведите k чисел - номера базовых станций, соответствующих одному из способов захвата.