#include<bits/stdc++.h>
//#pragma GCC optimize("O2")
using namespace std;
using ll = long long;
using ld = long double;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define sz(x) (int)x.size()
#define endl '\n'
const int mod = 1e9 + 7;
const int inf = 2e9 + 5;
const ll linf = 9e18 + 5;
int n, m;
const int N = 1e5 + 5;
const int M = 2e5 + 5;
vector<int> adj1[N];
bool mark[N];
int h[N];
int par[N];
int up[N];
vector<int> adj2[N + M];
bool mark2[N + M];
int block[N];
int bcnt[N];
int len[N + M];
int par2[N + M];
int total[N + M];
void init() {
}
void input() {
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int u, v;
cin >> u >> v;
// u = i; v = i + 1;
adj1[u].pb(v);
adj1[v].pb(u);
}
}
void dfshp(int u) {
mark[u] = true;
for (auto v : adj1[u]) {
if (!mark[v]) {
h[v] = h[u] + 1;
par[v] = u;
dfshp(v);
}
}
}
void dfsup(int u) {
mark[u] = true;
up[u] = h[u];
for (auto v : adj1[u]) {
if (!mark[v]) {
dfsup(v);
up[u] = min(up[u], up[v]);
}
else {
up[u] = min(up[u], h[v]);
}
}
}
void dfsbd(int u) {
mark[u] = true;
for (auto v : adj1[u]) {
if (!mark[v]) {
if (up[v] == h[u]) {
block[v] = v;
bcnt[v] = 1;
}
else {
block[v] = block[u];
}
dfsbd(v);
}
}
}
void dfslen(int u) {
if (u <= n) {
len[u] = bcnt[u];
}
else {
len[u] = 1;
}
for (auto v : adj2[u]) {
if (v != par2[u]) {
par2[v] = u;
dfslen(v);
len[u] += len[v] - 1;
}
}
}
void dfstotal(int u, const int x) {
total[u] = x;
for (auto v : adj2[u]) {
if (v != par2[u]) {
dfstotal(v, x);
}
}
}
pair<int, bool> dfscnt(int u) {
mark[u] = true;
int ans = 1;
bool path = true;
int pcnt = 0;
for (auto v : adj1[u]) {
if (!mark[v]) {
pair<int, bool> wef = dfscnt(v);
ans += wef.fi;
path &= wef.se;
}
else {
pcnt++;
}
}
if (pcnt == 2) {
path = false;
}
return mp(ans, path);
}
void solve() {
vector<int> roots;
ll ans = 0;
fill(mark + 1, mark + n + 1, false);
for (int u = 1; u <= n; u++) {
if (!mark[u]) {
// dfshp(u);
pair<int, bool> wef = dfscnt(u);
int nn = wef.fi;
if (wef.se) {
ans += (1ll * nn * (nn - 1) * (nn - 2) / 3;
}
else {
ans += (1ll * nn * (nn - 1) * (nn - 2));
}
roots.pb(u);
}
}
cout << ans;
/*
fill(mark + 1, mark + n + 1, false);
for (auto r : roots) {
if (!mark[r]) {
dfsup(r);
}
}
fill(mark + 1, mark + n + 1, false);
for (auto r : roots) {
if (!mark[r]) {
dfsbd(r);
}
}
for (int u = 1; u <= n; u++) {
bcnt[block[u]]++;
}
bcnt[0] = 0;
for (int u = 1; u <= n; u++) {
bool cut = false;
for (auto v : adj1[u]) {
if (par[v] == u && block[v] == v) {
cut = true;
}
}
if (cut) {
adj2[block[u]].pb(u + n);
adj2[u + n].pb(block[u]);
}
if (block[u] == u) {
adj2[block[u]].pb(par[u] + n);
adj2[par[u] + n].pb(block[u]);
}
}
int ans = 0;
for (auto r : roots) {
dfslen(r + n);
dfstotal(r + n, len[r + n]);
ans += mull(len[r + n], mull(len[r + n] - 1, len[r + n] - 2));
}
for (int u = 1; u <= n; u++) {
if (!mark2[u]) {
continue;
}
for (auto v : adj2[u]) {
if (par2[u] != v) {
ans -= mull(bcnt[u] - 1, mull(len[v], len[v] - 1));
ans %= mod;
}
}
ans -= mull(bcnt[u] - 1, mull(total[u] - len[u] + 1, total[u] - len[u]));
ans %= mod;
}
ans += mod;
ans %= mod;
cout << ans;*/
}
void output() {
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int number_of_testcases = 1;
//cin >> number_of_testcases;
while (number_of_testcases--) {
init();
input();
solve();
output();
}
return 0;
}
Compilation message
count_triplets.cpp: In function 'void solve()':
count_triplets.cpp:159:47: error: expected ')' before ';' token
159 | ans += (1ll * nn * (nn - 1) * (nn - 2) / 3;
| ~ ^
| )
