Koosaga의 문제

재현(Jaehyun)은 2019년 Petrozavodsk 겨울 캠프에서 그래프의 최대 컷 문제를 풀었다. 그래서 같은 성격의 문제를 하나 더 준비했다.

단순 연결 그래프 $G = (V, E)$가 주어진다. 정점은 $N$개, 간선은 $M$개이다. 다음 조건을 모두 만족하는 간선 부분집합 $S \subseteq E$의 개수를 구하라.

• $S$의 간선을 제거하면 그래프가 이분 그래프가 된다.
• $|S| \le 2$이다.
• $|T| < |S|$이면서 위의 두 조건을 만족하는 다른 부분집합 $T \subseteq E$가 존재하지 않는다.

$S$는 공집합일 수 있다.

첫 줄에 두 정수 $N$과 $M$이 주어진다($3 \le N \le 250000$, $N-1 \le M \le 250000$).

이후 $M$개의 줄에 공백으로 구분된 두 정수 $u_i$와 $v_i$가 주어진다($1 \le u_i, v_i \le N$). 이는 정점 $u_i$와 정점 $v_i$를 잇는 양방향 간선이다.

그래프에는 자기 루프와 중복 간선이 없으며, 연결되어 있다.

위 조건을 만족하는 간선 부분집합의 개수를 출력한다.