또 다른 간선

단순 무방향 그래프는 루프와 중복 간선이 없는 무방향 그래프이다.

평면 그래프는 간선들이 공통 끝점에서만 만나도록 평면 위에 그릴 수 있는 단순 무방향 그래프이다. 즉, 간선끼리 서로 교차하지 않게 그릴 수 있는 그래프이다.

독립 집합은 그래프에서 서로 인접하지 않은 정점들의 집합이다.

삼분 그래프는 정점들을 서로소인 세 개의 독립 집합으로 나눌 수 있는 단순 무방향 그래프이다.

평면 그래프가 주어진다. 이 그래프에 간선을 하나 추가하려고 한다. 어떤 간선을 추가해도 결과 그래프가 평면 그래프가 되지 않는다는 것을 알고 있다. 결과 그래프가 삼분 그래프가 되도록 간선을 하나 추가하는 방법의 수를 구하라.

결과 그래프는 단순 그래프여야 하므로 중복 간선이나 루프는 추가할 수 없다. $a-b$와 $b-a$는 같은 간선으로 보며 한 번만 센다.

첫 줄에 정점의 개수 $n$과 간선의 개수 $m$이 주어진다 ($3 \leq n, m \leq 3 \cdot 10^5$).

이후 $m$개의 줄에 각각 두 정수 $a$, $b$ ($1 \leq a, b \leq n$, $a \neq b$)가 주어진다. 이는 정점 $a$와 $b$ 사이에 간선이 있다는 뜻이다.

주어진 그래프는 위에서 설명한 조건을 만족함이 보장된다.

결과 그래프가 삼분 그래프가 되도록 간선을 추가하는 방법의 수를 정수 하나로 출력한다.

마지막 예제가 아름답고 간결하지 않은가?