← 返回题目列表

AtCoder · agc056_f

F. DFS 顺序中的度数序列

中文机器翻译题面 查看原题

分数: 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 如下。

picture

这里,顶点上写的数字代表它们在 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