?

Log in

No account? Create an account

rauf


Блог Алиева Рауфа

О жизни и о себе


Entries by category: экономика

Задача №2, посложнее:…
rauf
Задача №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

»