配点 : 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