Description：

给一个图，求有序三元组 $(s,c,f)$ 的对数满足存在一条简单路径从 $s$ 到 $c$ 再到 $f$ 。

$1\leqslant n\leqslant 10^5,1\leqslant m\leqslant 2\times 10^5$

Solution：

简单路径就是要求不经过重复的点，那么就不难想到 $tarjan$ 缩点双建立圆方树，问题在于怎么统计答案一种做法是把圆点权值设成 $-1$ ，方点权值为与它相邻的圆点个数，那么用树形 $DP$ 求一遍树上路径和即可，但是有一个更好理解的做法，就是用总方案数减去不合法的方案数，总方案数就是 $P^n_3$ ，不合法的方案数可以枚举 $c$ 所在的点双，那么如果另外两个点和它不在一个点双中，并且要经过同一个割点，那么就是不合法的，于是可以求出圆方树每个子树的 $siz$ ，另外两个点都在这棵子树中的方案数就为 $siz\times(siz-1)$ ，把这个累加，最后再扫描一下所有子树，对于每个子树，累加的值减去这个子树本身的值就是这个点作为中转点，另外两个点在这个点双的割点之外的方案数，一遍 $dfs$ 就可以了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<stack>

#include<vector>

#include<cctype>

#include<cstring>

using namespace std;

inline int rd()

{

	register int res = 0,f = 1;

	register char c = getchar();

	while(!isdigit(c))

	{

		if(c == '-')f = -1;

		c = getchar();

	}

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res * f;

}

int n,m;

#define MAXN 200010

namespace Graph

{

	struct edge

	{

		int to,nxt;

	}e[MAXN << 1];

	int edgenum = 0;

	int lin[MAXN] = {0};

	void add(int a,int b)

	{

		e[++edgenum] = (edge){b,lin[a]};lin[a] = edgenum;

		e[++edgenum] = (edge){a,lin[b]};lin[b] = edgenum;

		return;

	}

}

namespace Tree

{

	struct edge

	{

		int to,nxt;

	}e[MAXN << 1];

	int edgenum = 0;

	int lin[MAXN] = {0};

	void add(int a,int b)

	{

		e[++edgenum] = (edge){b,lin[a]};lin[a] = edgenum;

		e[++edgenum] = (edge){a,lin[b]};lin[b] = edgenum;

		return;

	}

}

long long ans;

int ptr;

int dfn[MAXN],low[MAXN],tot = 0;

stack<int> s;

bool circ[MAXN];

int sum;

void tarjan(int k)

{

	using namespace Graph;

	++sum;

	dfn[k] = low[k] = ++tot;

	circ[k] = true;

	s.push(k);

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(dfn[e[i].to] == 0)

		{

			tarjan(e[i].to);

			low[k] = min(low[k],low[e[i].to]);

			if(low[e[i].to] >= dfn[k])

			{

				int t;

				++ptr;

				do

				{

					t = s.top();s.pop();

					Tree::add(ptr,t);

				}while(t != e[i].to);

				Tree::add(ptr,k);

			}

		}

		else

		{

			low[k] = min(low[k],dfn[e[i].to]);

		}

	}

	return;

}

int siz[MAXN];

vector<int> v[MAXN];

bool vis[MAXN];

long long cnt = 0;

void dfs(int k)

{

	using namespace Tree;

	if(circ[k])siz[k] = 1;

	vis[k] = true;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(vis[e[i].to])continue;

		dfs(e[i].to);

		siz[k] += siz[e[i].to];

		v[k].push_back(siz[e[i].to]);

	}

	if(circ[k])return;

	v[k].push_back(sum - siz[k]);

	long long res = 0;

	for(vector<int>::iterator i = v[k].begin();i != v[k].end();++i)

	{

		res += 1ll * (*i) * (*i - 1) / 2;

	}

	for(vector<int>::iterator i = v[k].begin();i != v[k].end();++i)

	{

		cnt += res - 1ll * (*i) * (*i - 1) / 2;

	}

	return;

}

void work(int rt)

{

	while(!s.empty())s.pop();

	sum = 0;

	cnt = 0;

	tarjan(rt);

	dfs(rt);

	ans += 1ll * sum * (sum - 1) * (sum - 2) - 2 * cnt;

	return;

}

int main()

{

	scanf("%d%d",&n,&m);

	ptr = n;

	for(int i = 1;i <= m;++i)Graph::add(rd(),rd());

	for(int i = 1;i <= n;++i)

	{

		if(dfn[i] == 0)work(i);

	}

	cout << ans << endl;

	return 0;

}