Задача Upgrade

 Как в любом большом городе, в нашем достаточно много школ, каждая имеет свой сервер. Некоторые из них соединены между собой каналами двусторонней прямой связи. Каждый из каналов соединяет непосредственно  2 школы, любые две школы соединены не более, чем одним каналом. Образование  не имеет достаточно средств, потому  к каждой  школе ведет не более двух каналов. В процессе  работы информация передается с сервера-«отправителя»  на сервер– «получатель» через некоторые из наявных каналов, причем неважно, через какие. Но  многие из существующих каналов обустроены давно и не предназначены для передачи информации с большой скоростью. Наша лаборатория приняла решенние заменить часть каналов оптоволоконными таким образом: если информация могла попадать с сервера A на сервер B, то теперь она сможет пройти  с А на В через оптоволоконные каналы. Конечно, оптическое волокно стоит дорого, потому мы хотим заменить минимальное количество старых «медных» каналов на новые оптоволоконные, а избыточные  «медные»  законсервировать. Понятно, что каждый сервер умеет, как и ранее, «роутить» информацию, то есть пропускать ее далее, если существует канал связи.

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

Технические условия.  Программа UPGRADE  читает с клавиатуры 2числа n і m (1<=n<=105     0<=m<=105) – количество школ и количество каналов соответственно. Далее программа читает вm строках  каналы, по одному в строке. Каждый канал задан двумя целыми числами  Аі и Ві (1<= Аі, Ві <=n,  Аі<>Ві) – номера школ, которые соединяет канал с номером іГарантировано, что каждый канал задан не более одного раза. Программа выводит на экран одно единственное число – количество способов замены. Поскольку число может быть достаточно большим, выводить нужно по модулю 109+7(то есть - остаток от деления на это число).

Примеры

Ввод

5 4

1 2

2 3

1 3

4 5

Вывод

3

 

 

 

Ввод

2 1

1 2

 

 

 

Вывод

1

 

 

 

 

Комментарий к примеру. Существует три способа замены каналов:

{1,2,4},{1,3,4},{2,3,4}

 

© LIKT 1998-2018