{"raw_statement":[{"iden":"problem statement","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."},{"iden":"constraints","content":"*   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."},{"iden":"input","content":"Input 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$"},{"iden":"sample input 1","content":"3 2\n1 2\n2 3"},{"iden":"sample output 1","content":"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."},{"iden":"sample input 2","content":"4 6\n1 2\n1 3\n1 4\n2 3\n2 4\n3 4"},{"iden":"sample output 2","content":"19"},{"iden":"sample input 3","content":"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"},{"iden":"sample output 3","content":"90625632\n\n*   Be sure to find the count modulo $998244353$."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}