分数: 1600 点
问题陈述
给定的是整数 N 和 M。 求整数序列的数量 a=(a_1,a_2,\cdots,a_N) 可以按如下方式生成,模 998244353.
- 提供无向连通图 G 与 N 顶点和 M 边缘。 在这里, G 可能不包含自循环,但是 可能包含多边.
- 执行 DFS G 并让 a_i 是 i- 要访问的第一个顶点。 更准确地说,执行下面的伪代码可以得到 a.
a = empty array
dfs(v):
visited[v]=True
a.append(degree[v])
for u in g[v]:
if not visited[u]:
dfs(u)
dfs(arbitrary root)
这里,变量 g 代表图表 G 作为邻接表,其中 g[v] 是与该顶点相邻的顶点列表 v in 任意顺序.
例如,当 N=4,M=5,可以生成 a=(2,4,1,3),通过提供图表 G 如下。

这里,顶点上写的数字代表它们在 DFS 中被访问的顺序。 (DFS 从标记为 1。) 橙色箭头显示 DFS 中的转换,它们旁边的数字表示遍历边的顺序。
约束
- 2 \leq N \leq M \leq 10^6
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N M
输出
打印答案。
示例输入 1
2 2
示例输出 1
1
唯一可能的结果是 a=(2,2)。 请注意 G 可能有多边。
示例输入 2
3 4
示例输出 2
9
示例输入 3
10 20
示例输出 3
186225754
示例输入 4
100000 1000000
示例输出 4
191021899