/* @Date : 2025-08-16 18:17:55
@Author : hasan_86 */
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int maxN = 1e5 + 100;
const int MOD = 1e9 + 7;
ll power(ll x, int p) {
x %= MOD;
ll res = 1;
for (; p; p >>= 1) {
if (p & 1) res = res * x % MOD;
x = x * x % MOD;
}
return res;
}
vector<int> adj[maxN];
ll dp[maxN];
ll dp2[maxN];
ll mul[maxN];
int mark[maxN];
int par[maxN];
ll ans = 0;
void dfs(int x) {
dp[x] = 1;
mark[x] = 2;
int spec = 0;
for (int v : adj[x]) {
if (mark[v] == 0) {
par[v] = x;
dfs(v);
dp[x] = dp[x] * (dp[v] + 1) % MOD;
} else if (mark[v] == 1) {
spec = v;
}
}
if (spec != 0) {
int tmp = spec;
mul[spec] = dp[spec];
ll X = mul[spec];
ll S = 0;
ll Sp = 0;
while (tmp != x) {
S = (S + dp[tmp]) % MOD;
Sp = (Sp + dp[tmp]) % MOD;
mul[par[tmp]] = dp[par[tmp]] * power(dp[tmp] + 1, MOD - 2) % MOD;
X = X * mul[par[tmp]] % MOD;
tmp = par[tmp];
}
dp2[x] = (dp[x] - X + MOD) % MOD;
S = (S + dp2[x]) % MOD;
dp2[spec] = dp2[x] * mul[spec];
int v = spec;
while (v != x) {
dp2[v] = (dp2[v] - X + MOD) % MOD;
S = (S + dp2[v]) % MOD;
if (par[v] != x)
dp2[par[v]] = dp2[v] * mul[par[v]] % MOD;
v = par[v];
}
dp[x] = (S - Sp + MOD) % MOD;
}
mark[x] = 1;
ans = (ans + dp[x]) % MOD;
}
int main () {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, m;
cin >> n >> m;
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
adj[u].pb(v);
adj[v].pb(u);
}
dfs(1);
cout << ans << endl;
}
# | 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... |