Rauf Aliev (rauf) wrote,
Rauf Aliev
rauf

Categories:

Задача №2, посложнее:…

Задача №2, посложнее: «Перестройка». Первое правильное решение засабмичена Максимом Ивановым на 18-й минуте раунда. Вот она:



«В некоторой стране было ровно n городов и m дорог между ними. При этом в этой стране дорожная система была устроена следующим образом:



* между любыми двумя городами не больше одной дороги;

* никакая дорога не соединяет город с самим собой.



После смены власти новое правительство решило провести ряд реформ, среди которых есть реформа, затрагивающая дорожную систему страны. Эта реформа состоит из двух пунктов:



* разрушить одну из существующих дорог;

* построить новую дорогу, которой раньше не было, не ведущую из города в

него же.



Кроме этого, для улучшение экономических связей между городами, правительство хочет, чтобы после принятия дорожной реформы можно было добраться из любого города в любой другой. При этом не гарантируется, что это требование выполнялось до реформы.



Теперь правительство задумалось о том, сколько существует способов провести реформу. Помогите ему.



Первая строка содержит два целых числа n и m (1 ≤ n ≤ 100000, 0 ≤ m ≤ 200000). Следующие m строк содержат два числа ai и bi (1 ≤ ai, bi ≤ n, ai ≠ bi) — номера городов, которые соединяет i-я дорога.



Выведите одно целое число — количество способов провести реформу.



Например, при следующих входных данных

4 4

1 2

2 3

1 3

3 4



должно выводиться

8

»


Subscribe

  • Про пикник (pique-nique)

    Пока моется на мойке машина, делаю французский. И останавливаюсь на слове pique-nique в одном из упражнений. Стал копать, почему и откуда вылезло…

  • французская проза

    У Nana Beauregard есть книга, J'aime («Я люблю»). Так вот эта Нана в ней всеми своими 127 страницами признается в любви одним длиннющим…

  • О французском

    Оказалось, французы называют оргазм — La petite mort, «маленькая смерть». ( Правда, есть для этого и короткое нормальное слово, сoit). Раз такая…

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 0 comments