← 返回题目列表

AtCoder · jsc2022_final_a

A. 最大值和 Argmax

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

配点 : 500 点

問題文

N 頂点 M 有一个由边组成的简单、连通、无向图。 在顶部 它的编号最大为 1 减去 N 。 i 第一条边是顶点 A_i 与边缘 B_i 已连接。 请回答以下有关

(1,2,\cdots,N) 的排列 给出了 P=(P_1,P_2,\cdots,P_N) 的数量。 除以 998244353 求余数。

  • (非空)顶点集的子集 S 和 考虑由S 导出的子图是连接的情况。 这时,S 中包含的顶点 v 中,数字最大的是P_v 的值也是最大值。 换句话说,\max\{v|v \in S\}=\argmax\{P_v|v \in S\} 。
什么是诱导子图? 图

S 令 为 G 顶点的子集。 这时,G 可以得到第 S 的引导子图是一个顶点集为 S 且边缘设置为``G 两端有边 这是一张“ S 中包含的所有内容”的图表。

制約

  • 2 \leq N \leq 2 \times 10^5
  • N-1 \leq M \leq 2 \times 10^5
  • 1 \leq A_i,B_i \leq N
  • 给定的图很简单(没有自环或多边)并且是连通的。
  • 所有输入值均为整数

入力

输入是按以下格式从标准输入给出的。

N M
A_1 B_1
A_2 B_2
\vdots
A_M B_M

出力

打印答案。


入力例 1

4 4
1 2
2 4
4 1
3 4

出力例 1

3

满足条件的排列是 P=(1,2,3,4),(1,3,2,4),(2,3,1,4) 。 求放置超过

相反,P=(2,1,3,4) 等不满足条件。 例如,S=\{1,2\} ,然后S 中编号最大的顶点是 v=2 ,而P_v 是最大值 v=1 这就是原因。


入力例 2

10 10
4 8
1 3
6 10
6 7
8 7
1 5
4 2
5 2
3 9
9 10

出力例 2

126