AT_abc411_g [ABC411G] Count Cycles

There is an undirected graph $ G $ with $ N $ vertices and $ M $ edges. $ G $ does not contain self-loops, but may contain multi-edges. Vertices are numbered from $ 1 $ to $ N $ , and edges are numbered from $ 1 $ to $ M $ , with edge $ i $ connecting vertices $ U_i,V_i $ . Find the number, modulo $ 998244353 $ , of cycles contained in $ G $ . More formally, find the number, modulo $ 998244353 $ , of subsets $ \lbrace e_1,e_2,\dots,e_k\rbrace \subseteq \lbrace 1,2,\dots,M\rbrace\ (k\geq 2) $ of the given edge set that satisfy the following condition. - There exists a permutation $ (e_1',e_2',\dots,e_k') $ of $ (e_1,e_2,\dots,e_k) $ and a vertex sequence $ (v_1,v_2,\dots,v_k) $ such that all of the following hold: - $ v_1,v_2,\dots,v_k $ are pairwise distinct; - For all $ j\ (1\leq j\leq k) $ , edge $ e_j' $ connects vertices $ v_j,v_{(j\bmod k) + 1} $ .

The input is given from Standard Input in the following format: > $ N $ $ M $ $ U_1 $ $ V_1 $ $ U_2 $ $ V_2 $ $ \vdots $ $ U_M $ $ V_M $

Output the answer.

### Sample Explanation 1 As shown in the figure below, there are a total of $ 3 $ cycles. The numbers inside the circles and the numbers next to the lines represent vertex numbers and edge numbers, respectively. Red lines represent edges included in cycles, and black lines represent the other edges.  From left to right, these correspond to choosing edge sets $ \lbrace 1,2,3 \rbrace,\lbrace 2,3,4 \rbrace,\lbrace 1,4 \rbrace $ , respectively. ### Constraints - $ 2\leq N \leq 20 $ - $ 2\leq M \leq 2\times 10^5 $ - $ 1\leq U_i < V_i \leq N $ - All input values are integers.