18470번 - Counting Cactus 다국어

NEERC featured a number of problems about cactuses: connected undirected graphs in which every edge belongs to at most one simple cycle. Intuitively, a cactus is a generalization of a tree where some cycles are allowed. An example of a cactus from NEERC 2007 problem is given on the picture below.

Dreamoon has an undirected graph. Now he is wondering, how many subgraphs (subsets of edges) of his graph are cactuses? Can you help him find this value modulo 998 244 353?

The first line contains two integers n and m: the number of vertices and edges in the Dreamoon’s graph (1 ≤ n ≤ 13, 0 ≤ m ≤ n(n−1)/2).

The next m lines describe edges in the graph. The i-th of these lines contains two integers a_i and b_i (1 ≤ a_i, b_i ≤ n, a_i ≠ b_i), denoting an edge between vertices a_i and b_i. It is guaranteed that there are no multiple edges.

Output one integer: the number of cactus subgraphs of Dreamoon’s graph, modulo 998 244 353.

Sorry, Dreamoon.