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
  • 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