В некоторой стране было ровно n городов и m дорог между ними. При этом в этой стране дорожная система была устроена следующим образом:
между любыми двумя городами не больше одной дороги;
никакая дорога не соединяет город с самим собой.
После смены власти новое правительство решило провести ряд реформ, среди которых есть реформа, затрагивающая дорожную систему страны. Эта реформа состоит из двух пунктов:
разрушить одну из существующих дорог;
построить новую дорогу, которой раньше не было, не ведущую из города в него же.
Кроме этого, для улучшение экономических связей между городами, правительство хочет, чтобы после принятия дорожной реформы можно было добраться из любого города в любой другой. При этом не гарантируется, что это требование выполнялось до реформы.
Теперь правительство задумалось о том, сколько существует способов провести реформу. Помогите ему.
Первая строка содержит два целых числа n и m (1 ≤ n ≤ 100000, 0 ≤ m ≤ 200000). Следующие m строк содержат два числа a_i и b_i (1 ≤ a_i, b_i ≤ n, a_i ≠ b_i) — номера городов, которые соединяет i-я дорога.
Выведите одно целое число — количество способов провести реформу.