U104562 沙漠绿化

题目背景

土地荒漠化愈发严重,沙漠绿化刻不容缓!

题目描述

定义沙漠是满足如下性质的图: 没有重边和自环,且图中任意一条边至多属于一个简单环。 给定一片沙漠,从中删去任意多条边,使得删去边之后的图是一个森林,求有多少 种方法,答案对 998244353 取模。

输入格式

第一行两个整数 N, M ,表示图中的点数和边数。 接下来 M 行,每行两个整数 u, v,表示一条边的两个端点。

输出格式

输出到文件 desert.out 中。 输出一行一个整数表示答案。

说明/提示

对于 20% 的数据,图中只存在至多一个环; 对于 50% 的数据,满足任意一个点至多属于一个简单环; 对于 100% 的数据,1 ≤ N ≤ 3 ∗ 10^5,1 ≤ M ≤ 5 ∗ 10^5。