AT_fps_24_w 閉路

You are given a simple undirected graph $ G $ with $ N $ vertices and $ M $ edges, where the vertices are numbered $ 1 $ through $ N $ . The $ i $ -th edge connects vertex $ A_i $ and vertex $ B_i $ . Among all spanning subgraphs of $ G $ (that is, subgraphs covering all vertices of $ G $ ), count how many satisfy the following condition, and output the result modulo $ 998244353 $ : - There exists a cycle that contains both vertex $ 1 $ and vertex $ N $ .

The input is given from standard input in the following format: > $ N $ $ M $ $ A_1 $ $ B_1 $ $ A_2 $ $ B_2 $ $ \vdots $ $ A_M $ $ B_M $

Print the number of spanning subgraphs of $ G $ that satisfy the condition, modulo $ 998244353 $ .

### Partial Score This problem has partial scoring: - If you solve all datasets with $ N \leq 10 $ , you will earn $ 4 $ points. ### Sample Explanation 1 For example, the spanning subgraph consisting of edges $ 1 $ , $ 2 $ , $ 3 $ , and $ 5 $ satisfies the condition, because edges $ 2 $ , $ 3 $ , and $ 5 $ form a cycle that contains both vertex $ 1 $ and vertex $ 4 $ . ### Constraints - $ 3 \leq N \leq 16 $ - $ 3 \leq M \leq \binom{N}{2} $ - $ 1 \leq A_i < B_i \leq N $ - If $ i \neq j $ , then $ (A_i, B_i) \neq (A_j, B_j) $ - All input values are integers