eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Зміцнення мостів

Зміцнення мостів

Ліміт часу 2 секунди
Ліміт використання пам'яті 256 MiB

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

Байтландія складається з островів, деякі з яких з'єднано мостами. Кожен міст з'єднує два різних острови, довільні два острови з'єднані напряму не більше ніж одним мостом. Байтландці дуже бережливий народ, тому на кожен острів веде не більше двох мостів.

План заходу ще не готовий, але відомо, що план навчань танків буде таким: танки повинні будуть проїхати з одного острова на інший, користуючись деякими мостами, причому не важливо, якими саме мостами будуть користуватись танки. У Байтландії багато мостів, які було збудовано багато років тому і для танків зовсім не призначених. Тому міністр оборони вирішив зміцнити деякі мости. А конкретніше, він хоче зміцнити декілька мостів так, щоб не залежно від плану навчань, виконувалась умова: якщо була можливість переїхати з острова u на острів v, то після зміцнення деяких мостів можна переїхати з острова u на острів v по зміцненим мостам. При цьому зміцнення моста — дорога операція, тому міністр хоче зміцнити мінімальне число мостів.

Міністр оборони Байтландії хоче знати, скільки існує різних способів змізнення мінимального числа мостів. Два способи вважаються різними, якщо існує міст, який зміцнено у одному зі способів і не змізнено в іншому. Допоможіть міністру оборони знайти відповідь на хвилююче його довгий час питання. Оскільки відповідь може бути досить великою, виведіть її по модулю 10^9+7.

Вхідні дані

У першому рядку вхідного файлу задано два цілих числа n та m (1n10^5, 0m10^5) — кількість островів та кількість мостів у Байтландії відповідно.

У наступних m рядках задано мости, по одному у рядку. Кожен міст задано двома цілими числами: v_i та u_i(1v_i, u_in, v_iu_i) — номери островів, які з'єднує міст з номером i.

Гарантується, що кожен міст задано у вхідном файлі не більше одного раза.

Гарантується, що з кожного острова виходить не більше ніж два мости.

Вихідні дані

У вихідний файл виведіть єдине число: залишок від ділення кількості способів зміцнення мостів на число 10^9+7.

Приклад

Вхідні дані #1
5 4
1 2
2 3
1 3
4 5
Вихідні дані #1
3