Given a connected undirected graph $G = (V, E)$ with $n$ vertices and $m$ edges, where the $i$-th edge ($1 \le i \le m$) connects vertices $u_i$ and $v_i$ ($1 \le u_i, v_i \le n$).

For a subset of edges $E' \subseteq E$, we call $E'$ a cut set of graph $G$ if, after removing $E'$, there exist two vertices $u, v \in V$ such that $u \ne v$ and $u$ is not connected to $v$ in the resulting graph.

You want to find how many subsets of $E$ of size exactly $3$ are cut sets of $G$.

Input

The first line contains two integers $n$ and $m$, describing the number of vertices and edges in the graph.

The next $m$ lines each contain two integers $u, v$, describing an edge. The graph may contain multiple edges, but no self-loops.

Output

Output a single integer representing the number of such subsets.

Examples

Input 1

3 3
1 2
1 3
2 3

Output 1

1

Note 1

The valid subset is:

• $E' = \{ (1, 2), (1, 3), (2, 3) \}$.

Input 2

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

Output 2

19

Input 3

5 10
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5

Output 3

0

Input 4

3 4
1 2
1 2
2 3
2 3

Output 4

4

Subtasks

For all test cases, $2 \le n \le 2 \times 10^5$ and $3 \le m \le 5 \times 10^5$.

It is guaranteed that the given graph is a connected undirected graph and may contain multiple edges, but no self-loops.

• Property A: The graph is guaranteed to be generated as follows:
  • Select parameters $n, m$ such that $n \in [2, 2 \times 10^5]$ and $m \in [\max(3, n - 1), \min\left(\binom n2, 5 \times 10^5\right)]$.
  • Generate a tree with $n$ vertices.
  • Randomly add $m-n+1$ non-tree edges: each time, uniformly select an edge $(u, v)$ from all possible pairs such that no multiple edges or self-loops are created in the graph.