Counting Cactus
시간 제한2초메모리 제한512 MB
주어진 작은 그래프(n은 13 이하)에서 부분 그래프의 변 집합 가운데 연결되어 있고 모든 변이 많아야 하나의 단순 사이클에 속하는 것의 개수를 998244353으로 나눈 나머지를 구한다.
문제
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 ai and bi (1 ≤ ai, bi ≤ n, ai ≠ bi), denoting an edge between vertices ai and bi. 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.