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