만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

이중 클리크

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

요약
그래프에서 S는 서로 모두 간선으로 이어진 정점 집합이고, S 밖의 정점끼리는 간선이 없는 S의 개수를 10^9+7로 나눈 나머지로 구합니다.
난이도

보통10점 중 7점

유형
그래프, 조합론, 구현
정답자
아직 제출이 없습니다

문제

정점 nn개와 간선 mm개를 가진 무방향 그래프 GG가 주어진다. 정점의 집합은 VV, 간선의 집합은 EE이다.

GG의 보수 그래프를 G′G'라 하자. 보수 그래프는 GG와 같은 정점을 가진다. GG에서 정점 aa와 bb 사이에 간선이 없으면 G′G'에는 간선이 있고, GG에 간선이 있으면 G′G'에는 간선이 없다.

클리크는 모든 두 정점 사이에 간선이 있는 정점의 부분집합이다. 정점 부분집합 SS가 GG에서 클리크이고, V−SV - S가 G′G'에서 클리크이면 SS를 이중 클리크라고 한다. 공집합도 클리크로 본다.

그래프가 주어졌을 때, 이중 클리크의 개수를 109+710^9 + 7로 나눈 나머지를 구하라.

입력

첫 줄에 정수 nn과 mm이 주어진다 (1≤n,m≤2×1051 \le n, m \le 2 \times 10^5). 이어서 mm개의 줄에 정수 aa와 bb가 주어지며, 이는 정점 aa와 bb 사이에 간선이 있다는 뜻이다 (1≤a<b≤n1 \le a < b \le n). 같은 간선은 두 번 주어지지 않는다.

출력

이중 클리크의 개수를 109+710^9 + 7로 나눈 나머지를 한 줄에 출력한다.

예제1

  1. 예제 1

    입력
    3 3
    1 3
    1 2
    2 3
    
    예상 출력
    4