시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 256 MB | 6 | 1 | 1 | 16.667% |
В некоторой стране было ровно 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