F - Degree Sequence in DFS Order Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 1600 点

問題文

整数 N と M が与えられます． 以下の手順で生成されうる整数列 a=(a_1,a_2,\cdots,a_N) の個数を 998244353 で割った余りを求めてください．

  • N 頂点，M 辺からなる連結な無向グラフ G を用意する． ここで，G は自己ループを含んではならないが，多重辺を含んでもよい．
  • G 上で DFS を行い，i (1 \leq i \leq N) 番目に訪れた頂点の次数を a_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 に隣接する頂点を任意の順番で格納したリストである．

例えば，N=4,M=5 の時，a=(2,4,1,3) を生成することは可能です． そのためには，以下のようなグラフ G を用意すればよいです．

picture

ここで，頂点にかかれている数は，その頂点を DFS で何番目に訪れたかを表しています．（1 と書かれた頂点から DFS を開始しています．） また，オレンジ色の矢印は 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

Score : 1600 points

Problem Statement

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 N vertices and M edges. Here, G may not contain self-loops, but may contain multi-edges.
  • 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.
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)

Here, 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.

For example, when N=4,M=5, it is possible to generate a=(2,4,1,3), by providing the graph G as follows.

picture

Here, 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.

Constraints

  • 2 \leq N \leq M \leq 10^6
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M

Output

Print the answer.

Sample Input 1

2 2

Sample Output 1

1

The only possible result is a=(2,2). Note that G may have multi-edges.

Sample Input 2

3 4

Sample Output 2

9

Sample Input 3

10 20

Sample Output 3

186225754

Sample Input 4

100000 1000000

Sample Output 4

191021899