{"problem":{"name":"Connectivity 2","description":{"content":"Given is a simple undirected graph $G$ with $N$ vertices and $M$ edges. The vertices are numbered $1,2,\\dots,N$, the edges are numbered $1,2,\\dots,M$, and Edge $i$ connects Vertex $a_i$ and Vertex $b_","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":3000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc213_g"},"statements":[{"statement_type":"Markdown","content":"Given is a simple undirected graph $G$ with $N$ vertices and $M$ edges. The vertices are numbered $1,2,\\dots,N$, the edges are numbered $1,2,\\dots,M$, and Edge $i$ connects Vertex $a_i$ and Vertex $b_i$.  \nConsider removing zero or more edges from $G$ to get a new graph $H$. There are $2^M$ graphs that we can get as $H$. Among them, find the number of such graphs that Vertex $1$ and Vertex $k$ are directly or indirectly connected, for each integer $k$ such that $2 \\leq k \\leq N$.  \nSince the counts may be enormous, print them modulo $998244353$.\n\n## Constraints\n\n*   $2 \\leq N \\leq 17$\n*   $0 \\leq M \\leq \\frac{N(N-1)}{2}$\n*   $1 \\leq a_i \\lt b_i \\leq N$\n*   $(a_i, b_i) \\neq (a_j, b_j)$ if $i \\neq j$.\n*   All values in input are integers.\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":"abc213_g","tags":[],"sample_group":[["3 2\n1 2\n2 3","2\n1\n\nWe can get the following graphs as $H$.\n\n*   The graph with no edges. Vertex $1$ is disconnected from any other vertex.\n*   The graph with only the edge connecting Vertex $1$ and $2$. Vertex $2$ is reachable from Vertex $1$.\n*   The graph with only the edge connecting Vertex $2$ and $3$. Vertex $1$ is disconnected from any other vertex.\n*   The graph with both edges. Vertex $2$ and $3$ are reachable from Vertex $1$."],["5 6\n1 2\n1 4\n1 5\n2 3\n2 5\n3 4","43\n31\n37\n41"],["2 0","0"]],"created_at":"2026-03-03 11:01:13"}}