{"problem":{"name":"Lights Out on Connected Graph","description":{"content":"Given is an undirected graph $G$ consisting of $N$ vertices numbered $1$ through $N$ and $M$ edges numbered $1$ through $M$. It is guaranteed that $G$ is connected and contains no self-loops and no mu","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":3000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc105_f"},"statements":[{"statement_type":"Markdown","content":"Given is an undirected graph $G$ consisting of $N$ vertices numbered $1$ through $N$ and $M$ edges numbered $1$ through $M$. It is guaranteed that $G$ is connected and contains no self-loops and no multi-edges. Edge $i$ connects Vertex $a_i$ and Vertex $b_i$ bidirectionally. Each edge can be painted red or blue. Initially, every edge is painted red.\nConsider making a new graph $G^{\\prime}$ by removing zero or more edges from $G$. There are $2^M$ graphs that $G^{\\prime}$ can be. Among them, find the number of good graphs defined below, modulo $998244353$.\n$G^{\\prime}$ is said to be a _good graph_ when both of the following conditions are satisfied:\n\n*   $G^{\\prime}$ is connected.\n*   It is possible to make all edges blue by doing the following operation zero or more times.\n    *   Choose one vertex and change the color of every edge incident to that vertex, that is, red to blue and vice versa.\n\n## Constraints\n\n*   All values in input are integers.\n*   $1 \\leq N \\leq 17$\n*   $N-1 \\leq M \\leq N(N-1)/2$\n*   $G$ is connected and has no self-loops and no multi-edges.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$ $M$\n$a_1$ $b_1$\n$\\vdots$\n$a_M$ $b_M$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc105_f","tags":[],"sample_group":[["3 2\n1 2\n2 3","1\n\n*   The conditions are satisfied only if neither Edge $1$ nor Edge $2$ is removed.\n    *   In this case, we can make all edges blue by, for example, doing the operation for Vertex $2$.\n*   Otherwise, the graph gets disconnected and thus does not satisfy the condition."],["4 6\n1 2\n1 3\n1 4\n2 3\n2 4\n3 4","19"],["17 50\n16 17\n10 9\n16 10\n5 17\n6 15\n5 9\n15 11\n16 1\n8 13\n6 17\n15 3\n16 15\n11 3\n7 6\n1 4\n11 13\n10 6\n10 12\n3 16\n7 3\n16 5\n13 3\n12 13\n7 11\n3 12\n13 10\n1 12\n9 15\n11 14\n4 6\n13 2\n6 1\n15 2\n1 14\n15 17\n2 11\n14 13\n16 9\n16 8\n8 17\n17 12\n1 11\n6 12\n17 2\n8 1\n14 6\n9 7\n11 10\n5 14\n17 7","90625632\n\n*   Be sure to find the count modulo $998244353$."]],"created_at":"2026-03-03 11:01:14"}}