{"raw_statement":[{"iden":"problem statement","content":"Given are integers $N$ and $M$. Find the number of integer sequences $a=(a_1,a_2,\\cdots,a_N)$ that can be generated as follows, modulo $998244353$.\n\n*   Provide an undirected connected graph $G$ with $N$ vertices and $M$ edges. Here, $G$ may not contain self-loops, but **may contain multi-edges**.\n*   Perform DFS on $G$ and let $a_i$ be the degree of the $i$\\-th vertex to be visited. More accurately, execute the pseudo-code below to get $a$.\n\na = empty array\n\ndfs(v):\n    visited\\[v\\]=True\n    a.append(degree\\[v\\])\n    for u in g\\[v\\]:\n        if not visited\\[u\\]:\n            dfs(u)\n\ndfs(arbitrary root)\n\nHere, the variable $g$ represents the graph $G$ as an adjacency list, where $g[v]$ is the list of vertices adjacent to the vertex $v$ in **arbitrary order**.\nFor example, when $N=4,M=5$, it is possible to generate $a=(2,4,1,3)$, by providing the graph $G$ as follows.\n![image](https://img.atcoder.jp/agc056/3bfec17f881ae4cd27eccae94ebeae10.png)\nHere, the numbers written on vertices represent the order they are visited in the DFS. (The DFS starts at the vertex labeled $1$.) The orange arrows show the transitions in the DFS, and the numbers next to them represent the order the edges are traversed."},{"iden":"constraints","content":"*   $2 \\leq N \\leq M \\leq 10^6$\n*   All values in input are integers."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$ $M$"},{"iden":"sample input 1","content":"2 2"},{"iden":"sample output 1","content":"1\n\nThe only possible result is $a=(2,2)$. Note that $G$ may have multi-edges."},{"iden":"sample input 2","content":"3 4"},{"iden":"sample output 2","content":"9"},{"iden":"sample input 3","content":"10 20"},{"iden":"sample output 3","content":"186225754"},{"iden":"sample input 4","content":"100000 1000000"},{"iden":"sample output 4","content":"191021899"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}