e-olymp
Задачи

Перестройка

Перестройка

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

  • между любыми двумя городами не больше одной дороги;
  • никакая дорога не соединяет город с самим собой.

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

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

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

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

Входные данные

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

Выходные данные

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

Лимит времени 1 секунда
Лимит использования памяти 64 MiB
Входные данные #1
4 4
1 2
2 3
1 3
3 4
Выходные данные #1
8
Параллелепипед
Война