Counting Valid Triples in a Road Network

In the town of Bit, there is a network of (n) intersections connected by (m) bidirectional roads. Bit has recently been awarded the hosting of an Ironman triathlon. In this race, the contestants first run a long-distance course and then switch to biking to finish the race. The race route is planned in the following two steps:

1. Choose three distinct intersections (s), (c) and (f) to be the start, transition (where the athlete switches from running to cycling), and finish respectively.

2. Design a simple path (i.e. a path that does not visit any vertex more than once) from (s) to (f) that passes through (c).

The mayor needs your help to find out how many different choices of ((s, c, f)) are there such that in step 2 at least one valid simple (s)–(f) path going through (c) exists.

A key observation is that for a triple ((s, c, f)) the existence of a simple path from (s) to (f) that runs through (c) is equivalent to having two internally vertex–disjoint simple paths: one from (s) to (c) and another from (c) to (f). In graph–theoretical terms, this means that both (s) and (f) must be two–vertex–connected with (c), i.e. they lie in a common biconnected component (BCC) that contains (c). However, when (c) is an articulation point (i.e. it belongs to more than one BCC), a valid path from (s) to (f) passing through (c) exists if and only if (s) and (f) come from different biconnected components attached to (c).

More precisely, let the BCCs (blocks) containing (c) be (B_1, B_2, \dots, B_k). For each block (B_i), let the number of vertices in that block (except (c)) be (|B_i| - 1). Then:

• If (c) is not an articulation point (i.e. it belongs to a single BCC), any two distinct vertices in that block will satisfy the condition. The number of valid ordered pairs ((s,f)) (with (s) and (f) being distinct and not equal to (c)) is [ (|B_1| - 1) \times (|B_1| - 2). ]

• If (c) is an articulation point (i.e. (k > 1)), then valid choices require (s) and (f) come from two different blocks. The number of valid ordered pairs is [ 2 \times \sum_{1 \leq i < j \leq k} \Bigl((|B_i|-1) \times (|B_j|-1)\Bigr). ]

Your task is to compute the sum over all vertices (c) of the number of valid ordered pairs ((s,f)) corresponding to (c). This sum is the total number of valid ((s,c,f)) triples.

Note that the graph is given by (n) vertices (numbered from 1 to (n)) and (m) roads. Roads are bidirectional. There is no modulus in the output.

inputFormat

The first line contains two integers (n) and (m) -- the number of intersections and the number of roads, respectively. Each of the following (m) lines contains two integers (u) and (v) (1-based indices) representing a bidirectional road between intersections (u) and (v).

outputFormat

Output a single integer, the number of valid triples ((s, c, f)) such that there exists at least one simple path from (s) to (f) which passes through (c).

sample

3 2
1 2
2 3

2