Транспортная компания
(Время: 1 сек. Память: 16 Мб Сложность: 84%)
Транспортная компания «Crash & Co» занимается перевозкой запчастей для машин. Недавно в России открылось N отделений этой компании. Руководство компании приняло решение купить часть дорог между своими отделениями, чтобы обезопасить свои фуры от аварий. При этом купленных дорог должно быть по возможности минимальное количество, но они должны давать возможность добраться из любого отделения в любое другое. Вам, как программисту отдела покупок, было поручено в кратчайшие сроки определить количество различных вариантов покупки требуемого набора дорог.
Входные данные
В первой строке входного файла INPUT.TXT записано количество отделений компании N (1 ≤ N ≤ 20), и число различных дорог, соединяющих отделения M (1 ≤ M ≤ 5000). В следующих M строках записаны пары различных номеров отделений ai, bi (1 ≤ ai, bi ≤ N), соединенных дорогой.
Выходные данные
В выходной файл OUTPUT.TXT выведите требуемое количество способов.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 4 4
1 2
2 3
3 4
4 1 | 4 |
| 2 | 4 3
1 2
2 3
3 4 | 1 |
Пояснение
В первом примере возможны следующие варианты покупки дорог:
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
