B. Странное путешествие
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Маленький мальчик Игорь решил стать путешественником. Сначала он решил обойти все города в своей родной стране Ужляндии.

Как известно, в Ужляндии n городов, соединенных m двусторонними дорогами. Также известно, что между любыми двумя городами существует не больше одной дороги, но могут существовать дороги которые начинаются и заканчиваются в одном городе. Игорь решил спланировать свое путешествие заранее. Он называет хорошим путь, который посещает m - 2 дороги дважды, а остальные 2 дороги — по одному разу. Хороший путь начинается и заканчивается в любом городе. Не обязательно заканчивать путь в том же городе, в котором он начался.

Теперь Игорю стало интересно, сколько же путей его устраивают? Он считает два хороших пути различными, если различаются множества дорог, по которым он пройдет один раз. Помогите Игорю — посчитайте количество различных хороших путей.

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

В первой строке входных данных записано два целых числа n, m (1 ≤ n, m ≤ 106) — количество городов и дорог в Ужляндии соответственно. В каждой из следующих m строк находятся два целых числа u и v (1 ≤ u, v ≤ n), которые означают, что между городами u и v существует двусторонняя дорога.

Гарантируется, что между любыми двумя городами существует не больше одной дороги, в том числе, для каждого города существует не более одной дороги, которая ведет из него в него же самого.

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

Выведите одно целое число — количество различных хороших путей.

Примеры
Входные данные
5 4
1 2
1 3
1 4
1 5
Выходные данные
6
Входные данные
5 3
1 2
2 3
4 5
Выходные данные
0
Входные данные
2 2
1 1
1 2
Выходные данные
1
Примечание

В первом тестовом примере хорошими являются пути:

  • 2 → 1 → 3 → 1 → 4 → 1 → 5,
  • 2 → 1 → 3 → 1 → 5 → 1 → 4,
  • 2 → 1 → 4 → 1 → 5 → 1 → 3,
  • 3 → 1 → 2 → 1 → 4 → 1 → 5,
  • 3 → 1 → 2 → 1 → 5 → 1 → 4,
  • 4 → 1 → 2 → 1 → 3 → 1 → 5.

Кроме того, существуют хорошие пути, которые совпадают с каким-то из перечисленных выше, потому что совпадают множества дорог, по которым Игорь пройдет один раз:

  • 2 → 1 → 4 → 1 → 3 → 1 → 5,
  • 2 → 1 → 5 → 1 → 3 → 1 → 4,
  • 2 → 1 → 5 → 1 → 4 → 1 → 3,
  • 3 → 1 → 4 → 1 → 2 → 1 → 5,
  • 3 → 1 → 5 → 1 → 2 → 1 → 4,
  • 4 → 1 → 3 → 1 → 2 → 1 → 5,
  • и все эти пути в обратную сторону.

Таким образом, ответ равен 6.

Во втором примере Игорь не может пройти по всем дорогам.

В третьем примере он пройдет по одному разу по каждой из дорог.