#3323. 「SNOI2020」生成树

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: EntropyIncreaser

题目描述

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

输入格式

第一行两个整数 n,m ,表示图 G 的点数和边数。

接下来 m 行,每行两个用空格分隔的正整数 u, v(1\le u, v\le n) ,表示边 (u,v)\in G

输出格式

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

样例

样例输入

4 5
1 2
1 3
2 3
2 4
3 4

样例输出

8

数据范围与提示

对于所有数据, 1\le n\le m\le 5\times 10^5

  • 对于 10\% 的数据, 1\le n=m\le 2000
  • 对于另外 40\% 的数据, 1\le n,m\le 10^5 G 本身是仙人掌。
  • 对于余下 50\% 的数据,无特殊限制。