QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 256 MB Total points: 100

# 6225. 生成树

统计

给定无向连通图 $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\%$ 的数据,无特殊限制。