{"problem":{"name":"Degree Sequence in DFS Order","description":{"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$. *   Provide an undirected connected graph $G$ with ","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"agc056_f"},"statements":[{"statement_type":"Markdown","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.\n\n## Constraints\n\n*   $2 \\leq N \\leq M \\leq 10^6$\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\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"agc056_f","tags":[],"sample_group":[["2 2","1\n\nThe only possible result is $a=(2,2)$. Note that $G$ may have multi-edges."],["3 4","9"],["10 20","186225754"],["100000 1000000","191021899"]],"created_at":"2026-03-03 11:01:14"}}