Mock CCC '21 S5 - Clique and Independent Set

View as PDF

Points: 25 (partial)
Time limit: 0.25s
Memory limit: 1G

Problem types

You are given an undirected graph of vertices and edges. Compute the number of subsets of vertices which are cliques, where the vertices not in the subset form an independent set.

Input Specification

The first line contains two space-separated integers, and .

Each of the next lines contain two space-separated integers, and , indicating an edge between and . The input is guaranteed to contain no self-loops or parallel edges.

Output Specification

Count the number of valid subsets modulo .

Sample Input

3 3
1 2
1 3
2 3

Sample Output

4