시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 148 | 43 | 37 | 33.036% |
You are given an undirected graph G with n nodes and m edges. The set of vertices is V and the set of edges is E.
Let the Complement of G be G'. The Complement of a graph is a graph with all of the same nodes, but if there’s no edge between nodes a and b in G, then there is an edge between a and b in G', and if there is an edge between a and b in G, then there is no edge between a and b in G'.
A Clique is a subset of nodes that have an edge between every pair. A subset of nodes S is called a Double Clique if S forms a clique in G, and V − S forms a clique in G'. Note that an empty set of nodes is considered a clique.
Given a graph, count the number of double cliques in the graph modulo 109 + 7.
Each input will consist of a single test case. Note that your program may be run multiple times on different inputs. Each test case will begin with a line with two integers n and m (1 ≤ n, m ≤ 2 × 105), where n is the number of nodes and m is the number of edges in the graph. The nodes are numbered 1..n. Each of the next m lines will contain two integers a and b (1 ≤ a < b ≤ n), representing an edge between nodes a and b. The edges are guaranteed to be unique.
Output a single integer, which is the number of Double Cliques in the graph modulo 109 + 7.
3 3 1 3 1 2 2 3
4