#include<bits/stdc++.h>
using namespace std;
#define all(x) x.begin() , x.end()
#define pii pair<int, int>
#define piii pair<int, pii>
#define pll pair<ll, ll>
#define plll pair<ll, pll>
#define pb push_back
#define qb pop_back
#define F first
#define S second
#define wall cerr<<"--------------------------------------"<<endl
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#pragma GCC optimize("Ofast")
typedef long long ll;
typedef double db;
const ll INF = 1e9;
const ll maxn = 1e5 + 10;
const ll mod = 1e9 + 7;
ll n , m , h[maxn] , dp[maxn] , p[maxn] , par[maxn] , other[maxn];
bool tp[maxn] , mark[maxn];
vector<ll> g[maxn] , ar[maxn] , sum[maxn] , pre[maxn] , suf[maxn];
void dfs0(ll v)
{
mark[v] = 1;
for(auto u : g[v]){
if(u==p[v])continue;
if(mark[u]==1 && h[v]>h[u]){
par[v] = u;
tp[u] = true;
continue;
}
if(mark[u]==1)continue;
p[u] = v;
h[u] = h[v] + 1;
dfs0(u);
if(par[v]==-1)par[v] = par[u];
if(par[v]==v)par[v] = -1;
}
}
void dfs1(ll v)
{
mark[v] = 1;
dp[v] = 1;
other[v] = 1;
for(auto u : g[v]){
if(u==p[v] || mark[u]==1){
continue;
}
dfs1(u);
if(par[u]!=par[v] && par[u]!=v){
other[v] = (other[v] *(dp[u]+1))%mod;
}
dp[v] = (dp[v] * (dp[u]+1))%mod;
}
if(par[v]!=-1){
ar[par[v]].push_back(other[v]);
}
if(tp[v]==1){
dp[v] = 0;
ar[v].push_back(other[v]);
/**/
ll sz = ar[v].size();
for(int i=1; i<=sz; i++){
suf[v].push_back(0);
pre[v].push_back(0);
sum[v].push_back(1);
}
suf[v][sz-1]=ar[v][sz-1];
for(int i=sz-2; i>=0; i--){
suf[v][i] = (suf[v][i+1]*ar[v][i])%mod;
}
pre[v][0] = ar[v][0];
for(int i=1; i<sz; i++){
pre[v][i] = (pre[v][i-1]*ar[v][i])%mod;
}
sum[v][0]=1;
for(int i=1; i<sz; i++){
sum[v][i] = (sum[v][i-1]+pre[v][i-1])%mod;
}
/**/
// for(int i=0; i<sz; i++){
// cout<<ar[v][i]<<" ";
// }cout<<"\n";
// for(int i=0; i<sz; i++){
// cout<<suf[v][i]<<" ";
// }cout<<"\n";
// for(int i=0; i<sz; i++){
// cout<<pre[v][i]<<" ";
// }cout<<"\n";
// for(int i=0; i<sz; i++){
// cout<<sum[v][i]<<" ";
// }cout<<"\n";
/**/
for(int i=0; i<sz-1; i++){
//cout<<sum[v][i]*suf[v][i+1]<<" ";
dp[v] = (dp[v] + (sum[v][i]*suf[v][i+1])%mod)%mod;
}//cout<<"\n";
}
//cout<<v<<" : "<<dp[v]<<" , "<<other[v]<<"\n";
}
int main()
{
ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
cin>>n>>m;
for(int i=1; i<=m; i++){
int v,u; cin>>v>>u;
g[v].push_back(u);
g[u].push_back(v);
}
for(int i=1; i<=n; i++){
p[i] = -1;
par[i] = -1;
}
dfs0(1);
// for(int i=1; i<=n; i++){
// cout<<i<<" : "<<p[i]<<" , "<<par[i]<<"\n";
// }
for(int i=1; i<=n; i++){
mark[i] = 0;
}
dfs1(1);
ll ans = 0;
for(int i=1; i<=n; i++){
ans = (ans + dp[i])%mod;
}
// for(int i=1; i<=n; i++){
// cout<<i<<" : "<<dp[i]<<"\n";
// }cout<<"\n";
cout<<ans;
return 0;
}
/*
5 5
1 2
2 3
3 4
4 1
4 5
ans = 19;
*/
/*
5 4
1 2
1 3
2 4
2 5
ans = 17;
*/
/*
8 9
1 2
2 3
3 1
3 4
4 5
5 6
6 7
7 4
7 8
ans = 52;
*/
/*
by
_____ _____ _____ _____
/\ \ /\ \ /\ \ /\ \
/::\ \ /::\ \ /::\____\ /::\ \
/::::\ \ /::::\ \ /:::/ / \:::\ \
/::::::\ \ /::::::\ \ /:::/ / \:::\ \
/:::/\:::\ \ /:::/\:::\ \ /:::/ / \:::\ \
/:::/__\:::\ \ /:::/__\:::\ \ /:::/____/ \:::\ \
/::::\ \:::\ \ \:::\ \:::\ \ /::::\ \ /::::\ \
/::::::\ \:::\ \ ___\:::\ \:::\ \ /::::::\ \ _____ ____ /::::::\ \
/:::/\:::\ \:::\ \ /\ \:::\ \:::\ \ /:::/\:::\ \ /\ \ /\ \ /:::/\:::\ \
/:::/ \:::\ \:::\____\/::\ \:::\ \:::\____\/:::/ \:::\ /::\____\/::\ \/:::/ \:::\____\
\::/ \:::\ /:::/ /\:::\ \:::\ \::/ /\::/ \:::\ /:::/ /\:::\ /:::/ \::/ /
\/____/ \:::\/:::/ / \:::\ \:::\ \/____/ \/____/ \:::\/:::/ / \:::\/:::/ / \/____/
\::::::/ / \:::\ \:::\ \ \::::::/ / \::::::/ /
\::::/ / \:::\ \:::\____\ \::::/ / \::::/____/
/:::/ / \:::\ /:::/ / /:::/ / \:::\ \
/:::/ / \:::\/:::/ / /:::/ / \:::\ \
/:::/ / \::::::/ / /:::/ / \:::\ \
/:::/ / \::::/ / /:::/ / \:::\____\
\::/ / \::/ / \::/ / \::/ /
\/____/ \/____/ \/____/ \/____/
*/
//NOGHRE SHODANAM BAD NIST :_)
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
81 ms |
51696 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
12084 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
88 ms |
50972 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
97 ms |
53444 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
81 ms |
51696 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
