// In the Name of Allah
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast,unroll-loops,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,avx,avx2,sse4.2,popcnt,tune=native")
typedef long long ll;
#define F first
#define S second
#define pii pair<int, int>
#define pb push_back
#define pp pop_back
#define all(x) x.begin(), x.end()
const int mod = 1e9 + 7, N = 1e5 + 12;
vector<int> g[N], e[N];
int n, m, tc, c[N], h[N];
ll ans, dp[N];
bool mrk[N];
void ip() {
cin >> n >> m;
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
u--, v--;
g[u].pb(v), g[v].pb(u);
}
}
pii dfs1(int u, int par = -1) {
mrk[u] = true;
pii res = {-1, n};
for (auto i: g[u])
if (i != par) {
if (mrk[i]) {
if (!c[i])
res = {++tc, h[i]};
}
else {
h[i] = h[u] + 1;
pii tmp = dfs1(i, u);
if (tmp.S <= h[u])
res = tmp;
}
}
if (res.S > h[u])
c[u] = ++tc;
else
c[u] = res.F;
e[c[u]].pb(u);
return res;
}
void dfs(int u, int par = -1) {
vector<ll> v;
int sz = e[u].size(), t = -1;
for (auto i: e[u]) {
ll x = 1;
for (auto j: g[i])
if (c[j] != par && c[j] != u) {
dfs(c[j], u);
x = (x * (dp[c[j]] + 1)) % mod;
}
else if (c[j] == par)
t = v.size();
v.pb(x);
}
if (t != -1) {
vector<ll> z(sz), p(sz);
for (int i = t; i < sz; i++)
z[i - t] = v[i];
for (int i = 0; i < t; i++)
z[sz - t + i] = v[i];
p[0] = 1;
for (int j = 1; j < sz - 1; ++j) {
ll i = z[j];
p[j] = (p[j - 1] * (i + 1)) % mod;
}
reverse(z.begin() + 1, z.end());
ll x = 1;
for (int j = 0; j < sz - 1; ++j) {
ll i = z[j];
x = (x * i) % mod;
dp[u] = (dp[u] + x * p[sz - j - 1]) % mod;
}
if (sz == 1)
dp[u] = z[0];
}
cout << u << ' ' << dp[u] << endl;
vector<ll> z(sz, 1);
for (int i = 0; i < sz - 1; i++)
for (int j = 0; j < sz; ++j)
z[j] = (z[j] * v[(j + i) % sz]) % mod, ans = (ans + z[j]) % mod;
if (sz == 1)
ans = (ans + v[0]) % mod;
}
void solve() {
dfs1(0);
dfs(1);
cout << ans;
}
int32_t main() {
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
ip(), solve();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
6492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
6492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
6492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
6492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
