EduBrick

J. Отказоустойчивое множество

3000 мс · 256 МБ · всё или ничего

Множество серверов AA называется отказоустойчивым, если при выходе из строя любого одного канала до каждого сервера вне AA всё ещё можно передать данные хотя бы от одного сервера из AA.

Найдите наименьший размер такого множества и количество способов его выбрать по модулю 109+710^9 + 7.

Формат ввода

В первой строке nn и mm (2≤n≤2⋅1052 \le n \le 2 \cdot 10^5, 1≤m≤2⋅1051 \le m \le 2 \cdot 10^5). В каждой из следующих mm строк — концы канала. Кратных каналов и петель нет, граф связен.

Формат вывода

Выведите два числа: наименьший размер отказоустойчивого множества и количество способов его выбрать по модулю 109+710^9 + 7.

Примеры

ввод
5 5
1 2
2 3
3 4
3 5
4 5
вывод
2 3
Разбор идеи от автора задачи. Сначала попробуйте сами.
Войдите, чтобы отправлять решения.