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 <iostream>
#include <vector>

using namespace std;

typedef long long ll;

const int MAX_N = 1e5 + 5;

vector<int> out_adj [MAX_N];
vector<int> in_adj [MAX_N];

int color [MAX_N];

void dfs (int u, int c, vector<ll> &cnt, int &edgec, int &ok) {
  color[u] = c;
  cnt[c]++;
  
  for (int nxt : out_adj[u]) {
    edgec++;
    if (color[nxt] == -1) {
      dfs(nxt, (c + 1) % 3, cnt, edgec, ok);
    } else if (color[nxt] != (c + 1) % 3) {
      ok = 0;
    }
  }

  for (int prv : in_adj[u]) {
    if (color[prv] == -1) {
      dfs(prv, (c + 2) % 3, cnt, edgec, ok);
    } else if (color[prv] != (c + 2) % 3) {
      ok = 0;
    }
  }
}

typedef long long ll;

ll sq (ll x) {
  return x * x;
}

int main () {
  ios::sync_with_stdio(false);

  int n, m;
  cin >> n >> m;

  for (int i = 0; i < m; i++) {
    int u, v;
    cin >> u >> v;

    out_adj[u].push_back(v);
    in_adj[v].push_back(u);
  }

  for (int i = 1; i <= n; i++) {
    color[i] = -1;
  }

  ll ans = 0;
  for (int i = 1; i <= n; i++) {
    if (color[i] == -1) {
      vector<ll> c (3, 0);
      int edgec = 0;
      int ok = 1;
      dfs(i, 0, c, edgec, ok);

      if (!ok) {
        ans += sq(c[0] + c[1] + c[2]);
      } else if (c[0] * c[1] * c[2] == 0) {
        ans += edgec;
      } else {
        ans += c[0] * c[1] + c[0] * c[2] + c[1] * c[2];
      }
    }
  }
  cout << ans << endl;
}