Маленький мальчик Игорь решил стать путешественником. Сначала он решил обойти все города в своей родной стране Ужляндии.
Как известно, в Ужляндии n городов, соединенных m двусторонними дорогами. Также известно, что между любыми двумя городами существует не больше одной дороги, но могут существовать дороги которые начинаются и заканчиваются в одном городе. Игорь решил спланировать свое путешествие заранее. Он называет хорошим путь, который посещает m - 2 дороги дважды, а остальные 2 дороги — по одному разу. Хороший путь начинается и заканчивается в любом городе. Не обязательно заканчивать путь в том же городе, в котором он начался.
Теперь Игорю стало интересно, сколько же путей его устраивают? Он считает два хороших пути различными, если различаются множества дорог, по которым он пройдет один раз. Помогите Игорю — посчитайте количество различных хороших путей.
Выходные данные
Выведите одно целое число — количество различных хороших путей.
Примечание
В первом тестовом примере хорошими являются пути:
- 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.
Во втором примере Игорь не может пройти по всем дорогам.
В третьем примере он пройдет по одному разу по каждой из дорог.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 4
1 2
1 3
1 4
1 5
|
6
|
|
2
|
5 3
1 2
2 3
4 5
|
0
|
|
3
|
2 2
1 1
1 2
|
1
|