C. Укрепление мостов

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

Байтландия состоит из островов, некоторые из которых соединены мостами. Каждый мост соединяет два различных острова, любые два острова соединены напрямую не более чем одним мостом. Байтландцы очень экономный народ, поэтому на каждый остров ведут не более двух мостов.

План мероприятия еще не готов, но известно, что план учений танков будет таким: танки должны будут проехать с одного острова на другой, пользуясь некоторыми мостами, причем не важно, какими именно мостами будут пользоваться танки. В Байтландии много мостов, которые были построены много лет назад и для танков совершенно не предназначены. Поэтому министр обороны решил укрепить некоторые мосты. А конкретно, он хочет укрепить несколько мостов так, чтобы вне зависимости от плана учений, выполнялось условие: если была возможность переехать с острова u на остров v, то после укрепления некоторых мостов можно переехать с острова u на остров v по \textbf{укрепленным} мостам. При этом укрепление моста – дорогая операция, поэтому министр хочет укрепить минимальное число мостов.

Министр обороны Байтландии хочет знать, сколько существует различных способов укрепления минимального числа мостов. Два способа считаются различными, если существует мост, который укреплен в одном из способов и не укреплен в другом. Помогите министру обороны найти ответ на волнующий его долгое время вопрос. Поскольку ответ может быть довольно большим, выведите его по модулю 10⁹+7.

Формат входного файла

В первой строке входного файла заданы два целых числа n и m (1 ≤ n ≤ 10⁵, 0 ≤ m ≤ 10⁵) – количество островов и количество мостов в Байтландии соответственно. В следующих m строках заданы мосты, по одному в строке. Каждый мост задан двумя целыми числами: v_i и u_i (1 ≤ v_i, u_i ≤ n, v_i ≠ u_i) – номера островов, которые соединяет мост с номером i.

Гарантируется, что каждый мост задан во входном файле не более одного раза.

Гарантируется, что из каждого острова выходят не более чем два моста.

Формат выходного файла

В выходной файл выведите единственное число: остаток от деления количества способов укрепления мостов на число 10⁹+7.

Пример:

В первом примере существует три способа укрепления мостов: укрепить мосты с номерами {1, 2, 4 }, либо {1, 3, 4 }, либо {2, 3, 4 }.

Источник: Командный чемпионат школьников Карелии по программированию, 4 ноября 2012

Обсудить       Отправить решение



Версия для печати