Problem Description

The Kingdom of Paken consists of $N$ cities numbered from $1$ to $N$ and $M$ roads numbered from $1$ to $M$. For each $i$ ( $1 \leq i \leq M$ ), road $i$ connects city $u_i$ and city $v_i$ bidirectionally.

Penguin-kun is planning a trip within the Kingdom of Paken. To make his plan, he wants to know the following information:

• How many integer pairs $(l, r)$ satisfying $1 \leq l \leq r \leq M$ exist such that the following condition is met:
• There exists a path starting from some city $X$, passing through roads $l$, $l+1$, $\cdots$, $r$ exactly once in any order, and returning to city $X$.

This task is too difficult for Penguin-kun. Therefore, please find the answer on his behalf.

(16:30 Update:)

• In the path, roads other than $l$, $l+1$, $\cdots$, $r$ cannot be used.
• It is possible to pass through city $X$ during the path.

Input Format

The input is given from the standard input in the following format:

$N$ $M$ $u_1$ $v_1$ $u_2$ $v_2$ $\vdots$ $u_M$ $v_M$

Output Format

Output the answer.

Sample Input and Output

Sample Input #1

4 4
1 2
2 3
3 4
2 4

Sample Output #1

1

Sample Input #2

5 8
2 3
3 1
2 3
3 2
2 5
3 2
1 5
2 1

Sample Output #2

3

Sample Input #3

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

Sample Output #3

6

Sample Input #4

8 12
7 1
7 1
3 7
3 7
6 3
6 3
5 7
5 7
6 8
6 8
5 8
5 8

Sample Output #4

18

Notes/Hints

Constraints

• $1 \leq N, M \leq 5 \times 10^4$
• $1 \leq u_i, v_i \leq N$
• $u_i \neq v_i$
• All inputs are integers

Subtasks

1. (200 points) $N, M \leq 3000$
2. (150 points) $v_i = u_{i+1}$ ( $1 \leq i \leq M-1$ )
3. (350 points) $M$ is even, $(u_{2i-1}, v_{2i-1}) = (u_{2i}, v_{2i})$ ( $1 \leq i \leq \frac{M}{2}$ ), $\{u_i, v_i\} \neq \{u_j, v_j\}$ ( $|i-j| \geq 2$ )
4. (100 points) No additional constraints

Sample Explanation 1

The pair $(l, r)$ that satisfies the condition in the problem statement is only $(2, 4)$. For $(l, r) = (2, 4)$, there exists a path, for example, starting from city $2$, passing through road $4$, road $3$, and road $2$ in this order, and returning to city $2$. This input satisfies the constraints of subtasks $1, 4$.

Sample Explanation 2

This input satisfies the constraints of subtasks $1, 4$.

Sample Explanation 3

This input satisfies the constraints of subtasks $1, 2, 4$.

Sample Explanation 4

This input satisfies the constraints of subtasks $1, 3, 4$. Original idea: penguinman

见题面 Input 部分

见题面 Output 部分