Перебудова#3512
У деякій країні було рівно міст та доріг між ними. При цьому у цій країні система доріг була влаштована наступним чином:
між довільними двома містами не більше однієї дороги;
ніяка дорога не з'єднує місто саме з собою.
Після зміни влади новий уряд вирішив провести ряд реформ, серед яких є реформа, яка стосується дорожньої системи країни. Ця реформа складається з двох пунктів:
зруйнувати одну з існуючих доріг;
побудувати нову дорогу, якої раніше не було, яка не веде з міста у нього ж.
Крім цього, для покращення економічних зв'язків між містами, уряд хоче, щоб після прийняття дорожньої реформи можна було дістатися з довільного міста у довільне інше. При цьому не гарантується, що ця вимога виконувалася до реформи.
Тепер уряд задумався над тим, скільки існує способів провести реформу. Допоможіть йому.
Перший рядок містить два цілих числа і (1 \leq n \leq 100\,000, 0 \leq m \leq 200\,000). Наступні рядків містять по два числа a_i та b_i (1 \leq a_i, b_i \leq n, a_i \neq b_i) — номери міст, які з'єднує -та дорога.
Виведіть одне ціле число — кількість способів провести реформу.
Приклад 1