Размещение данных
(Время: 2 сек. Память: 64 Мб Сложность: 63%)
Телекоммуникационная сеть крупной IT-компании содержит n серверов, пронумерованных от 1 до n. Некоторые пары серверов соединены двусторонними каналами связи, всего в сети m каналов. Гарантируется, что сеть серверов устроена таким образом, что по каналам связи можно передавать данные с любого сервера на любой другой сервер, возможно с использованием одного или нескольких промежуточных серверов.
Множество серверов A называется отказоустойчивым, если при недоступности любого канала связи выполнено следующее условие. Для любого не входящего в это множество сервера X существует способ передать данные по остальным каналам на сервер X хотя бы от одного сервера из множества A.
На рис. 1 показан пример сети и отказоустойчивого множества из серверов с номерами 1 и 4. Данные на сервер 2 можно передать следующим образом. При недоступности канала между серверами 1 и 2 – с сервера 4, при недоступности канала между серверами 2 и 3 – с сервера 1. На серверы 3 и 5 при недоступности любого канала связи можно по другим каналам передать данные с сервера 4.
Рис. 1. Пример сети и отказоустойчивого множества серверов.
В рамках проекта группе разработчиков компании необходимо разместить свои данные в сети. Для повышения доступности данных и устойчивости к авариям разработчики хотят продублировать свои данные, разместив их одновременно на нескольких серверах, образующих отказоустойчивое множество. Чтобы минимизировать издержки, необходимо выбрать минимальное по количеству серверов отказоустойчивое множество. Кроме того, чтобы узнать, насколько гибко устроена сеть, необходимо подсчитать количество способов выбора такого множества, и поскольку это количество способов может быть большим, необходимо найти остаток от деления этого количества способов на число 109 + 7.
Требуется написать программу, которая по заданному описанию сети определяет следующие числа: k – минимальное количество серверов в отказоустойчивом множестве серверов, c – остаток от деления количества способов выбора отказоустойчивого множества из k серверов на число 109 + 7.
Входные данные
Первая строка входного файла INPUT.TXT содержит целые числа n и m – количество серверов и количество каналов связи соответственно (2 ≤ n ≤ 200 000, 1 ≤ m ≤ 200 000). Следующие m строк содержат по два целых числа и описывают каналы связи между серверами. Каждый канал связи задается двумя целыми числами: номерами серверов, которые он соединяет.
Гарантируется, что любые два сервера соединены напрямую не более чем одним каналом связи, никакой канал не соединяет сервер сам с собой, и для любой пары серверов существует способ передачи данных с одного из них на другой, возможно с использованием одного или нескольких промежуточных серверов.
Выходные данные
В выходной файл OUTPUT.TXT выведите два целых числа, разделенных пробелом: k – минимальное число серверов в отказоустойчивом множестве серверов, c – количество способов выбора отказоустойчивого множества из k серверов, взятое по модулю 109 + 7.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 5 5
1 2
2 3
3 4
3 5
4 5 | 2 3 |
Пояснение к примеру
В приведенном примере отказоустойчивыми являются следующие множества из двух серверов: {1, 3}, {1, 4}, {1, 5}.
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
