|
Мафия в городе
(Время: 1 сек. Память: 16 Мб Сложность: 47%)
Об этом еще никто не знает, но многие догадываются – мафия уже в городе. Поговаривают, что в планах главы мафиозного клана захват контроля над всем городом, однако поначалу он решил ограничиться захватом основных линий связи города.
В городе находятся n базовых телефонных станций, некоторые пары которых соединены двусторонними каналами связи. Для удобства, занумеруем базовые станции целыми числами от 1 до n, канал связи в этом случае задается парой чисел (u, v) – номерами станций, которые он соединяет.
Будем говорить, что канал связи (u, v) – контролируется мафией, если захвачена, либо станция u, либо станция v (либо обе).
Глава мафиозного клана хочет контролировать все каналы связи, захватив при этом как можно меньше базовых станций. Ваша задача помочь службе безопасности телефонной компании, составив возможный план захвата и определив количество таких планов.
Входные данные
Первая строка входного файла INPUT.TXT содержит два целых числа: n и m
(2 ≤ n ≤ 18, 0 ≤ m). Каждая из последующих m строк описывает один канал связи и содержит по два целых числа: u и v (1 ≤ u, v ≤ n, u ≠ v) – номера базовых станций, соединенных этим каналом связи. Любая пара станций соединена не более, чем одним каналом.
Выходные данные
В первой строке выходного файла OUTPUT.TXT выведите два числа: k и c – соответственно, минимальное количество базовых станций, которые необходимо захватить для того, чтобы контролировать все каналы связи, и число способов захватить такое количество станций так, чтобы контролировать все каналы связи.
Во второй строке выведите k чисел – номера базовых станций, соответствующих одному из способов захвата.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 3 3
1 2
2 3
3 1 | 2 3
1 2 |
| 2 | 5 4
1 2
1 3
1 4
1 5 | 1 1
1 |
Пояснение
В первом примере существует три способа захватить две станции так, чтобы контролировать все каналы связи: {1, 2}, {1, 3}, {2, 3}.
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |
