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;
const int N = 100010;
int uni[N],dis[N],sz[N][3],n,m,tag[N],num[N],deg[N];
long long ans;
int getfa(int pos) {
  if (uni[pos] == pos) return pos;
  int ret = getfa(uni[pos]);
  (dis[pos] += dis[uni[pos]]) %= 3;
  return uni[pos] = ret;
}
int main() {
  int x,y,a,b;
  scanf("%d%d",&n,&m);
  for (int i = 1 ; i <= n ; ++ i)
    uni[i] = i, dis[i] = 0;
  for (int i = 1 ; i <= m ; ++ i) {
    scanf("%d%d",&x,&y);
    a = getfa(x), b = getfa(y);
    ++ deg[x];
    ++ deg[y];
    if (a != b) {
      uni[b] = a;
      dis[b] = (dis[x] + 4 - dis[y]) % 3;
    } else {
      if ((dis[y] - dis[x] + 3) % 3 == 1);
      else tag[a] = 1;
    }
  }
  for (int i = 1 ; i <= n ; ++ i) {
    num[getfa(i)] += deg[i];
    tag[getfa(i)] |= tag[i];
    sz[getfa(i)][(dis[i] + 3) % 3] ++;
  }
  for (int i = 1 ; i <= n ; ++ i) {
    if (getfa(i) != i) continue;
    if (tag[i]) ans += 1ll * (sz[i][0] + sz[i][1] + sz[i][2]) * (sz[i][0] + sz[i][1] + sz[i][2]);
    else {
      if ((!sz[i][0]) || (!sz[i][1]) || (!sz[i][2]))
	ans += num[i] / 2;
      else
	ans += 1ll * sz[i][0] * sz[i][1] + 1ll * sz[i][1] * sz[i][2] + 1ll * sz[i][2] * sz[i][0];
    }
  }
  cout << ans << endl;
  return 0;
}