그래프

면접 대비

시간 제한2초메모리 제한1024 MB

요약

그래프에서 간선이 없는 정점 쌍 중 간선을 추가하면 단순 사이클이 정확히 하나 생기는 쌍의 개수를 구합니다.

난이도: 보통10점 중 5점
유형: 그래프, DFS, 트리
정답자: 아직 제출이 없습니다

문제

많은 해 전에 알프는 생일 선물로 무방향 그래프를 받았다. 최근 짐을 정리하다가 그 그래프를 발견하고 크게 놀랐다. 한동안 그래프를 가지고 놀던 알프는 궁금해졌다. 간선이 없는 정점 쌍 중에서, 그 사이에 간선을 추가하면 정점이 중복되지 않는 사이클(단순 사이클)이 정확히 하나 새로 생기는 쌍은 몇 개인가?

입력

첫 줄에 정수 $n, m$ ( $1 \le n, m \le 10^5$ )이 주어진다. 각각 정점의 개수와 간선의 개수이다. 이어서 $m$ 개의 줄에 정수 쌍 $u, v$ ( $1 \le u, v \le n$ )가 주어지며, 이는 그래프의 간선을 나타낸다.

출력

조건을 만족하는 정점 쌍의 개수를 한 줄에 출력한다.

예제2

예제 1
입력
```
5 4
1 2
2 3
3 4
4 5
```
예상 출력
```
6
```
예제 2
입력
```
5 5
1 2
2 3
1 3
3 4
4 5
```
예상 출력
```
1
```