Задача 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} |
|||