Cow Friendship Formation

FJ has (N) cows labeled (1,2,\ldots,N) and initially there are (M) pairs of friends among them. The cows leave the farm one by one for vacation: on day (i) the cow with label (i) leaves. At the moment a cow leaves the farm, all of its friends still on the farm become pairwise friends (if they are not already friends). Your task is to determine the total number of new friendship pairs that are formed by these events.

More formally, let the initial set of friendship pairs be given. On day (i) when cow (i) leaves, if its current friend list among cows with labels greater than (i) is (F) and if some two cows in (F) are not already direct friends (either originally or via previous departures), then a new friendship is established between them. Compute the total number of new edges added over all days.

Note: All formulas are written in (\LaTeX) format.

inputFormat

The first line of input contains two integers \(N\) and \(M\) (\(2 \le N \le 2\times10^5\), \(1 \le M \le 2\times10^5\)). Each of the next \(M\) lines contains two integers \(u\) and \(v\) (\(1 \le u, v \le N\) and \(u \neq v\)) representing an initial friendship between cow \(u\) and cow \(v\). The friendship relation is bidirectional.

It is guaranteed that no friendship pair appears more than once.

outputFormat

Output a single integer: the total number of new friendship pairs formed after all cows have left.

Important: An edge formed later is only counted if it did not exist originally (or was not formed by an earlier departure event).

sample

3 1
2 3

0