[2019CCPC秦皇岛] F Forest Program 点双连通分量

给出一个$n\le 3e5$的仙人掌，然后求问有多少种删边的方案，使得这个仙人掌变成一个森林，仙人掌保证一条边不会被两个简单环共用。
找出所有的环，那么环中的边只要至少删掉一条即可满足，而剩下所有的非环的边则可删可不删，直接求出所有的点双连通分量，答案为$\prod (2^s-1)2^t$，s是每个点双中的边数，t是剩下的边数。
注意两点一线的点双要特判掉。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll; 
const int mod=998244353;
const int N=3e5+7;
vector<int> go[N];
int pre[N],bccno[N],dfs_clock=0,bcc_cnt=0;
vector<int> bcc[N];
stack< pair<int,int> > s;
int dfs(int u,int fa) {
	int lowu=pre[u]=++dfs_clock;
	int child=0;
	for(auto &v:go[u]) {
		pair<int,int> e={u,v};
		if(!pre[v]) {
			s.push(e);
			child++;
			int lowv=dfs(v,u);
			lowu=min(lowu,lowv);
			if(lowv>=pre[u]) {
				bcc_cnt++;
				bcc[bcc_cnt].clear();
				for(;;) {
					pair<int,int> x=s.top();
					s.pop();
					if(bccno[x.first]!=bcc_cnt) {
						bcc[bcc_cnt].push_back(x.first);
						bccno[x.first]=bcc_cnt;
					}
					if(bccno[x.second]!=bcc_cnt) {
						bcc[bcc_cnt].push_back(x.second);
						bccno[x.second]=bcc_cnt;
					}
					if(x.first==u&&x.second==v) 
						break;
				}
			}
		}
		else if(pre[v]<pre[u]&&v!=fa) {
			s.push(e);
			lowu=min(lowu,pre[v]);
		}
	} 
	return lowu; 
}
ll ans=1; 
ll fpow(ll x,ll y) {
	ll ans=1;
	while(y) {
		if(y&1) ans=(ans*x)%mod;
		x=(x*x)%mod;
		y>>=1;
	}
	return ans;
}
int main() {
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++) {
		int u,v;
		scanf("%d%d",&u,&v);
		go[u].push_back(v);
		go[v].push_back(u);
	}
	for(int i=1;i<=n;i++) {
		dfs(i,0);
	}
	int tot=m;
	for(int i=1;i<=bcc_cnt;i++) {
		if(bcc[i].size()==2) continue;
		else {
			ans=(ans*(fpow(2LL,bcc[i].size())-1))%mod; 
			tot-=bcc[i].size();	
		}
	}
	ans=(ans*fpow(2LL,tot))%mod; 
	printf("%lld\n",ans); 
	return 0;
}