Description

There is an undirected graph with $N$ vertices and $M$ edges. The graph has no multiple edges and no self-loops.

If $a<b<c$ and there is an edge between $a$ and $b$, and there is also an edge between $a$ and $c$, then an edge will be added between $b$ and $c$.

Find the final number of edges.

Input Format

The first line contains two integers $N$ and $M$.

The next $M$ lines each contain two integers $a_i$ and $b_i$, indicating that there is an edge connecting $a_i$ and $b_i$.

Output Format

Only one line with one integer, representing the final number of edges.

6 4
1 2
1 4
4 6
4 5

6

7 6
2 3
2 6
2 7
1 3
1 4
1 5

16

Hint

Explanation for Sample 1

You need to add two edges, $(2,4)$ and $(5,6)$.

Constraints and Limits

For $100\%$ of the testdata, it is guaranteed that $1\le N,M\le 10^5$, $1\le a_i<b_i\le N$.

Notes

This problem is translated from Canadian Computing Olympiad 2019 Day 2 T2 Marshmallow Molecules。

Translated by ChatGPT 5