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 open(s) freopen( s".in", "r", stdin ), freopen( s".out", "w", stdout )
#define LL long long
#define MAXN 100005
#define MAXM 200005

int N, M;
int hd[MAXN], nxt[MAXM], to[MAXM], tot(1);
int cnt[5], c[MAXN], sum;
bool flg;
LL ans;

void Add( int x, int y ){
	nxt[++tot] = hd[x]; hd[x] = tot; to[tot] = y;
	nxt[++tot] = hd[y]; hd[y] = tot; to[tot] = x;
}

int Get( int x, bool fg ){return fg ? ( x + 2 ) % 3 : ( x + 1 ) % 3;}

void DFS( int x ){
	cnt[c[x] + 1]++;
	for ( int i = hd[x]; i; i = nxt[i] ){
		sum++;
		if ( c[to[i]] >= 0 ){
			if ( Get( c[x], i & 1 ) != c[to[i]] ) flg = 1;
		}else c[to[i]] = Get( c[x], i & 1 ), DFS( to[i] );
	}
}
 
int main(){
	scanf( "%d%d", &N, &M );
	for ( int i = 1; i <= M; ++i ){
		int x, y; scanf( "%d%d", &x, &y ); Add( x, y );
	}
	memset( c, -1, sizeof c );
	for ( int i = 1; i <= N; ++i ){
		if ( c[i] < 0 ){
			flg = 0; c[i] = 0; sum = 0;
			cnt[1] = cnt[2] = cnt[3] = 0;
			DFS( i );
			if ( flg ) ans += 1ll * ( cnt[1] + cnt[2] + cnt[3] ) * ( cnt[1] + cnt[2] + cnt[3] );
			else if ( cnt[1] == 0 || cnt[2] == 0 || cnt[3] == 0 ) ans += sum / 2;
			else ans += (LL)cnt[1] * cnt[2] + (LL)cnt[2] * cnt[3] + (LL)cnt[3] * cnt[1];
		}
	}
	printf( "%lld", ans );
	return 0;
}