#include <bits/stdc++.h>
using namespace std;
#define int long long
const int modulo = 998244353;
const int div2 = 499122177;
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n,m;
cin >> n >> m;
vector<vector<int>> adj(n+1);
vector<pair<int,int>> edges(m+1);
for(int i=1;i<=m;i++){
int a,b;
cin >> a >> b;
adj[a].emplace_back(b);
adj[b].emplace_back(a);
edges.emplace_back(a,b);
}
vector<int> par(n+1);
vector<vector<int>> cleanadj(n+1);
vector<bool> visited(n+1);
vector<int> depth(n+1);
// TEMP
vector<pair<int,int>> backedges;
// TEMP END
{
function<void(int,int,int)> dfs = [&](int x,int p,int dep){
par[x]=p;
visited[x]=true;
depth[x]=dep;
for(int&i:adj[x])if(i!=p){
if(visited[i]){
if(depth[i]<depth[x]){
backedges.emplace_back(i,x);
}
} else {
dfs(i,x,dep+1);
cleanadj[x].emplace_back(i);
}
}
};
for(int i=1;i<=n;i++)if(!visited[i])dfs(i,0,0);
}
vector<bool> picked(n+1);
vector<int> pre(n+1);
function<void(int,int)> dfs = [&](int x,int curr){
visited[x]=true;
if(picked[x])curr++;
pre[x]=curr;
for(int&i:cleanadj[x])dfs(i,curr);
};
int ans = 0;
for(int mask = 0;mask<(1<<n);mask++){
bool works = true;
for(int i=0;i<n;i++){
if(mask&(1<<i) and par[i+1]==0)works=false;
else if(mask&(1<<i))picked[i+1]=true;
else picked[i+1]=false;
}
if(!works)continue;
int curr = 1;
fill(visited.begin(),visited.end(),false);
for(int i=1;i<n;i++)if(!visited[i])dfs(i,0);
for(auto&[a,b]:backedges){
if(pre[b]-pre[a]!=depth[b]-depth[a] and pre[b]-pre[a]!=0){
curr*=2;
curr%=modulo;
}
}
ans+=curr;
ans%=modulo;
}
cout << (((ans*m)%modulo)*div2)%modulo << '\n';
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |