모스토비

레오나르트 오일러가 유명한 쾨니히스베르크 다리 문제를 풀었을 때, 그는 자신이 그래프 이론이라는 새로운 수학 분야를 발견했다는 사실을 알지 못했다!

안타깝게도 쾨니히스베르크 다리 문제는 이 시대 프로그래머에게 너무 쉬웠다. 그래서 오일러는 또 다른 문제인 자그레브 다리 문제를 생각해 냈다!

자그레브의 다리는 노드 $n$개와 간선 $m$개로 이루어진 그래프를 이룬다. 간선은 다리를, 노드는 강 가운데 있는 섬을 나타낸다. 이 그래프는 연결되어 있다. 즉, 간선을 따라 어떤 노드에서든 다른 어떤 노드로 갈 수 있다. 오일러는 간선을 제거했을 때 그래프가 연결되지 않게 되는 간선이 몇 개인지 물었다.

이 문제 역시 오늘날 유명하다는 사실을 오일러는 몰랐다(그 망할 Codeforces 블로그들). 그래서 이 문제의 저자는 더 어려운 문제를 내기로 했다. 간선이 잇는 두 노드를 제거했을 때 남은 $n - 2$개의 노드가 연결되지 않게 되는 간선은 몇 개인가?

첫 번째 줄에 노드의 수 $n$과 간선의 수 $m$이 주어진다 ($4 \le n \le 100\,000$, $n - 1 \le m \le 300\,000$).

이어지는 $m$개의 줄에는 각각 정수 $a_i$와 $b_i$ ($1 \le a_i, b_i \le n$)가 주어진다. 이는 노드 $a_i$와 $b_i$가 간선으로 연결되어 있다는 뜻이다.

자기 자신으로 가는 간선이나 중복된 간선은 없다.

조건을 만족하는 간선의 개수를 한 줄에 출력한다.

첫 번째 예제 설명:

간선 $(1, 3)$과 그 간선이 잇는 노드 $1$, $3$을 제거하면, 남은 그래프는 노드 $2$와 노드 $4$라는 두 개의 연결 요소로 나뉜다. 즉 연결되지 않는다. 이 성질을 가진 간선은 이것 하나뿐이라는 것을 쉽게 확인할 수 있다.

두 번째 예제 설명:

조건을 만족하는 간선은 $(1, 2)$, $(2, 4)$, $(2, 6)$, $(2, 5)$이다.