검 세기

Michael은 그래프 가게를 열 계획이다. 그래프 가게는 다양한 크기와 모양의 그래프를 전문적으로 파는 가게다. Michael은 시장 조사를 철저히 했고, 사업은 매우 수익성이 좋아 보인다. 그는 원하는 그래프를 무엇이든 만들어 내는 그래프 생성기까지 발명했다.

하지만 사업을 시작하는 데 걸림돌이 하나 있다. Michael은 각 그래프의 가격을 어떻게 매겨야 하는지 모른다. 몇 주 동안 자료를 읽은 끝에, 그는 그래프의 가치를 검 부분 그래프(sword subtree)의 개수로 계산할 수 있다는 것을 알아냈다. 서로 다른 여섯 개의 정점(A부터 F까지의 문자로 나타내자)이 다음 간선들을 가질 때 검 부분 그래프를 이룬다(그림 참고):

• A는 B와 연결된다.
• B는 A와 D와 연결된다.
• C는 D와 연결된다.
• D는 B, C, E, F와 연결된다.
• E는 D와 연결된다.
• F는 D와 연결된다.

두 검 부분 그래프 $T_1$과 $T_2$는 $T_1$에는 있고 $T_2$에는 없는 간선 e가 하나라도 있으면 서로 다른 것으로 본다.

지식이 풍부한 사람이자 그의 사업 파트너인 당신의 임무는 Michael이 만든 그래프에서 검 부분 그래프의 개수를 세는 것을 돕는 것이다. 무방향 그래프가 주어졌을 때, 검 부분 그래프의 개수를 세는 프로그램을 작성하라.

입력의 첫 줄에는 두 정수 $N$과 $M$이 주어진다. ($1 ≤ N, M ≤ 100\,000$) 이는 그래프의 정점 수와 간선 수를 나타낸다. 다음 $M$개의 줄에는 무방향 간선의 양 끝점 $u_i$와 $v_i$가 주어진다. ($1 ≤ u_i, v_i ≤ N$) 이 간선들로 표현되는 그래프에는 중복 간선이나 자기 루프가 없다는 것이 보장된다.

주어진 그래프의 검 부분 그래프 개수를 나타내는 정수 하나를 출력한다.