시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 (추가 시간 없음) 512 MB 11 8 7 70.000%

문제

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

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

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

입력

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

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

출력

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

예제 입력 1

6 7
1 2
2 3
3 6
2 4
4 5
1 6
2 5

예제 출력 1

7

출처