17098번 - Boomerangs

당신에게 그래프 G가 주어진다. G는 N개의 정점과 M개의 간선으로 이루어져 있으며, 연결그래프이다. 또한 양 끝 정점이 같은 간선이나 동일한 간선이 여러개 존재하지 않는다.

어떠한 정점 u, v, w가 존재해 u와 v를 잇는 간선이 있고, v와 w를 잇는 간선이 있다면, 이 두 간선을 묶어 부메랑이라고 부른다.

해당하는 두 간선을 없앴을 때에 몇 개의 간선을 지나도 서로 오갈 수 없는 정점 쌍이 존재하게 하는 부메랑의 개수를 구하여라.

첫 줄에 N과 M이 주어진다. (1 ≤ N, M ≤ 5×10⁵)

M개의 줄에 걸쳐 u와 v로 간선의 정보가 주어지며, 이는 u번 정점과 v번 정점을 잇는 간선이 존재함을 의미한다. (1 ≤ u, v ≤ N, u ≠ v)

해당하는 두 간선을 없앴을 때에 연결된 컴포넌트의 수를 증가시키는 부메랑의 개수를 출력한다.