C. Close to Gray
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

You are given a simple undirected graph $$$G$$$ with $$$n$$$ vertices and $$$m$$$ black edges. The $$$i$$$-th black edge connects vertices $$$u_i$$$ and $$$v_i$$$. For every pair of distinct vertices not connected by a black edge, there is a white edge between them.

We call two distinct vertices $$$x$$$ and $$$y$$$ close to gray if both of the following conditions hold:

  • It is possible to travel from $$$x$$$ to $$$y$$$ using only black edges.
  • It is possible to travel from $$$x$$$ to $$$y$$$ using only white edges.

Find the number of unordered pairs $$$(x, y)$$$, where $$$1 \leq x \lt y \leq n$$$, that are close to gray.

Input

The first line contains two integers $$$n$$$ and $$$m$$$, representing the number of vertices and black edges, respectively.

Each of the next $$$m$$$ lines contains two integers $$$u_i$$$ and $$$v_i$$$, indicating that there is a black edge between them.

  • $$$2 \leq n \leq 5 \times 10^5$$$
  • $$$0 \leq m \leq 5 \times 10^5$$$
  • $$$1 \leq u_i, v_i \leq n$$$
  • $$$u_i \neq v_i$$$
  • There are no multiple edges between the same pair of vertices.
Output

Output a single integer representing the number of unordered pairs that are close to gray.

Examples
Input
4 4
1 3
2 3
1 4
2 4
Output
2
Input
6 11
1 2
1 3
1 5
2 3
2 4
2 6
3 4
3 5
3 6
4 5
5 6
Output
4
Input
252525 0
Output
0