U104562 沙漠绿化
题目背景
土地荒漠化愈发严重,沙漠绿化刻不容缓!
题目描述
定义沙漠是满足如下性质的图:
没有重边和自环,且图中任意一条边至多属于一个简单环。
给定一片沙漠,从中删去任意多条边,使得删去边之后的图是一个森林,求有多少 种方法,答案对 998244353 取模。
输入格式
第一行两个整数 N, M ,表示图中的点数和边数。
接下来 M 行,每行两个整数 u, v,表示一条边的两个端点。
输出格式
输出到文件 desert.out 中。 输出一行一个整数表示答案。
说明/提示
对于 20% 的数据,图中只存在至多一个环;
对于 50% 的数据,满足任意一个点至多属于一个简单环; 对于 100% 的数据,1 ≤ N ≤ 3 ∗ 10^5,1 ≤ M ≤ 5 ∗ 10^5。