У деякій країні було рівно 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-та дорога.
Виведіть одне ціле число — кількість способів провести реформу.