{"problem":{"name":"Cycle","description":{"content":"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 spa","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":5000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"fps_24_w"},"statements":[{"statement_type":"Markdown","content":"You are given a simple undirected graph $G$ with $N$ vertices and $M$ edges, where the vertices are numbered $1$ through $N$.  \nThe $i$\\-th edge connects vertex $A_i$ and vertex $B_i$.  \nAmong 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$:\n\n*   There exists a cycle that contains both vertex $1$ and vertex $N$.\n\n## Constraints\n\n*   $3 \\leq N \\leq 16$\n*   $3 \\leq M \\leq \\binom{N}{2}$\n*   $1 \\leq A_i < B_i \\leq N$\n*   If $i \\neq j$, then $(A_i, B_i) \\neq (A_j, B_j)$\n*   All input values are integers\n\n## Input\n\nThe input is given from standard input in the following format:\n\n$N$ $M$\n$A_1$ $B_1$\n$A_2$ $B_2$\n$\\vdots$\n$A_M$ $B_M$\n\n## Partial Score\n\nThis problem has partial scoring:\n\n*   If you solve all datasets with $N \\leq 10$, you will earn $4$ points.\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"fps_24_w","tags":[],"sample_group":[["4 5\n1 2\n1 3\n1 4\n2 4\n3 4","8\n\nFor 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$."],["6 15\n1 2\n1 3\n2 3\n1 4\n2 4\n3 4\n1 5\n2 5\n3 5\n4 5\n1 6\n2 6\n3 6\n4 6\n5 6","20448"]],"created_at":"2026-03-03 11:01:14"}}