#PQJ318x6225. QOJ 318_6225

    ID: 2912 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:省选赛事:SNOI 2020

QOJ 318_6225

给定无向连通图 𝐺 ,已知 𝐺 在删掉一条边后是一颗仙人掌(仙人掌:不存在两个拥有公共边的简单环的无向联通图),求 𝐺 的生成树个数。结果对 998244353 取模。

输入格式

第一行两个整数 𝑛 , 𝑚 ,表示图 𝐺 的点数和边数。

接下来 𝑚 行,每行两个用空格分隔的正整数 𝑢 , 𝑣 ( 1 ≤ 𝑢 , 𝑣 ≤ 𝑛 ) ,表示边 ( 𝑢 , 𝑣 ) ∈ 𝐺 。

输出格式

输出一行一个整数,表示图 𝐺 的生成树个数对 998244353 取模的结果

样例数据 样例输入 4 5 1 2 1 3 2 3 2 4 3 4 样例输出 8 子任务

对于所有数据, 1 ≤ 𝑛 ≤ 𝑚 ≤ 5 × 10 5 。

对于 10 % 的数据, 1 ≤ 𝑛

𝑚 ≤ 2000 。 对于另外 40 % 的数据, 1 ≤ 𝑛 , 𝑚 ≤ 10 5 且 𝐺 本身是仙人掌。 对于余下 50 % 的数据,无特殊限制。