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 <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 100005;
const int go[3][2] = {{2, 1}, {0, 2}, {1, 0}};
long long ans;
int n, x, y, m, cnte, cnt[3], siz, sum, flag, col[maxn], h[maxn];
struct edge_t { int to, next, w; } edge[maxn * 2];
void ins(int x, int y, int z) {
    edge[++cnte].to = y;
    edge[cnte].next = h[x];
    edge[cnte].w = z;
    h[x] = cnte;
}
void dfs(int now, int c) {
    ++cnt[col[now] = c];
    ++siz;
    for (int i = h[now]; i; i = edge[i].next) {
        sum += edge[i].w;
        if (col[edge[i].to] == -1) dfs(edge[i].to, go[c][edge[i].w]);
        else if (col[edge[i].to] != go[c][edge[i].w]) flag = 1;
    }
}
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; ++i) col[i] = -1;
    for (int i = 1; i <= m; ++i) {
        scanf("%d %d", &x, &y);
        ins(x, y, 1);
        ins(y, x, 0);
    }
    for (int i = 1; i <= n; ++i) {
        if (col[i] == -1) {
            flag = siz = sum = cnt[0] = cnt[1] = cnt[2] = 0;
            dfs(i, 0);
            if (flag) ans += (long long) siz * siz;
            else if (cnt[0] == 0 || cnt[1] == 0 || cnt[2] == 0) ans += sum;
            else ans += (long long) cnt[0] * cnt[1] + (long long) cnt[1] * cnt[2] + (long long) cnt[2] * cnt[0];
        }
    }
    printf("%lld", ans);
}