이중 클리크
시간 제한2초메모리 제한512 MB
그래프에서 S는 서로 모두 간선으로 이어진 정점 집합이고, S 밖의 정점끼리는 간선이 없는 S의 개수를 10^9+7로 나눈 나머지로 구합니다.
문제
정점 개와 간선 개를 가진 무방향 그래프 가 주어진다. 정점의 집합은 , 간선의 집합은 이다.
의 보수 그래프를 라 하자. 보수 그래프는 와 같은 정점을 가진다. 에서 정점 와 사이에 간선이 없으면 에는 간선이 있고, 에 간선이 있으면 에는 간선이 없다.
클리크는 모든 두 정점 사이에 간선이 있는 정점의 부분집합이다. 정점 부분집합 가 에서 클리크이고, 가 에서 클리크이면 를 이중 클리크라고 한다. 공집합도 클리크로 본다.
그래프가 주어졌을 때, 이중 클리크의 개수를 로 나눈 나머지를 구하라.
입력
첫 줄에 정수 과 이 주어진다 (). 이어서 개의 줄에 정수 와 가 주어지며, 이는 정점 와 사이에 간선이 있다는 뜻이다 (). 같은 간선은 두 번 주어지지 않는다.
출력
이중 클리크의 개수를 로 나눈 나머지를 한 줄에 출력한다.