Емблема центру  www.olymp.vinnica.ua     netoi.org.ua
Центр олімпіад школярів в Iнтернеті
Likt-PMG17
м.Вiнниця


Годинник
 
Upgrade

Задача Upgrade

 Як і  у будь якому  великому місті, у нашому досить багато шкіл, кожна має свій сервер. Деякі із них з’єднані між собою каналами двостороннього прямого зв’язку. Кожен із каналів сполучає безпосередньо 2 школи, будь-які дві школи з’єднані не більше, ніж одним каналом. Освіта не має багато коштів, тому до кожної школи веде не більше, ніж 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}


© Всеукраїнський віртуальний центр олімпіад школярів "ОЛІМП"