Автор: | Russian Code Cup 2012 | Ограничение времени: | 2 сек | |
Входной файл: | input.txt | Ограничение памяти: | 256 Мб | |
Выходной файл: | output.txt |
В некоторой стране было ровно N городов и M дорог между ними. При этом в этой стране дорожная система была устроена следующим образом:
После смены власти новое правительство решило провести ряд реформ, среди которых есть реформа, затрагивающая дорожную систему страны. Эта реформа состоит из двух пунктов:
Кроме этого, для улучшения экономических связей между городами, правительство хочет, чтобы после принятия дорожной реформы можно было добраться из любого города в любой другой. При этом не гарантируется, что это требование выполнялось до реформы.
Теперь правительство задумалось о том, сколько существует способов провести реформу. Помогите ему.
Первая строка содержит два целых числа N и M. Следующие M строк содержат два числа ai, bi — номера городов, которые соединяет i-я дорога.
Выведите одно целое число — количество способов провести реформу.
1 ≤ N ≤ 105
0 ≤ M ≤ 2 ⋅ 105
1 ≤ ai, bi ≤ N, ai ≠ bi