Problem: We have a grid with N rows and N columns. The cell at the i-th row and j-th column is denoted (i, j).

Initially, M of the cells are painted black, and all other cells are white. Specifically, the cells (a_1, b_1), (a_2, b_2), ..., (a_M, b_M) are painted black.

Snuke will try to paint as many white cells black as possible, according to the following rule:

* If two cells (x, y) and (y, z) are both black and a cell (z, x) is white for integers 1≤x,y,z≤N, paint the cell (z, x) black.



Find the number of black cells when no more white cells can be painted black.

Constraints

* 1≤N≤10^5
* 1≤M≤10^5
* 1≤a_i,b_i≤N
* All pairs (a_i, b_i) are distinct.

Input

The input is given from Standard Input in the following format:


N M
a_1 b_1
a_2 b_2
:
a_M b_M


Output

Print the number of black cells when no more white cells can be painted black.

Examples

Input

3 2
1 2
2 3


Output

3


Input

2 2
1 1
1 2


Output

4


Input

4 3
1 2
1 3
4 4


Output

3

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
using namespace std;
 
#define ll long long
#define pb push_back
 
const int maxn = 2e5 + 20;

vector<int> adj[maxn] , ver;

int h[maxn] , t[3] , from[maxn] , to[maxn];

bool visited[maxn] , f;

void dfs(int v)
{
	visited[v] = 1;
	ver.pb(v);

	for(auto e : adj[v])
	{
		int u = from[e] ^ to[e] ^ v;
		if(!visited[u])
			dfs(u);
	}
}

void color(int v)
{
	visited[v] = 1;
	for(auto e : adj[v])
	{
		int u = from[e] ^ to[e] ^ v;

		int vu = (h[v] + (u == to[e]? 1 : -1) + 3) % 3;
		if(!visited[u])
		{
			h[u] = vu;
			color(u);
		}
		else if(h[u] != vu)
			f = 1;
	}

	t[h[v]]++;
}

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 a , b;
		cin >> a >> b;
		a-- , b--;

		adj[a].pb(i);
		adj[b].pb(i);

		from[i] = a , to[i] = b;
	}

	ll res = 0;
	for(int i = 0; i < n; i++)
		if(!visited[i])
		{
			ver.clear();
			dfs(i);

			for(auto v : ver)
				visited[v] = 0;

			f = 0;
			memset(t , 0 , sizeof t);

			for(auto v : ver)
				if(!visited[v])
					color(v);

			if(f)
				res += (ll)ver.size() * (ll)ver.size();
			else if(t[0] && t[1] && t[2])
			{
				for(int i = 0; i < 3; i++)
					res += 1LL * t[i] * t[(i + 2) % 3];
			}
			else
			{
				int edge = 0;
				for(auto v : ver)
					edge += (int)adj[v].size();
				res += edge / 2;
			}
		}

	cout << res << endl;
}