Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

data structures

graphs

*2700

No tag edit access

The problem statement has recently been changed. View the changes.

×
I. Desert

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou are given an undirected graph of $$$N$$$ nodes and $$$M$$$ edges, $$$E_1, E_2, \dots E_M$$$.

A connected graph is a cactus if each of it's edges belogs to at most one simple cycle. A graph is a desert if each of it's connected components is a cactus.

Find the number of pairs $$$(L, R)$$$, ($$$1 \leq L \leq R \leq M$$$) such that, if we delete all the edges except for $$$E_L, E_{L+1}, \dots E_R$$$, the graph is a desert.

Input

The first line contains two integers $$$N$$$ and $$$M$$$ ($$$2 \leq N \leq 2.5 \times 10^5$$$, $$$1 \leq M \leq 5 \times 10^5$$$). Each of the next $$$M$$$ lines contains two integers. The $$$i$$$-th line describes the $$$i$$$-th edge. It contains integers $$$U_i$$$ and $$$V_i$$$, the nodes connected by the $$$i$$$-th edge ($$$E_i=(U_i, V_i)$$$). It is guaranteed that $$$1 \leq U_i, V_i \leq N$$$ and $$$U_i \neq V_i$$$.

Output

The output contains one integer number – the answer.

Examples

Input

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

Output

20

Input

2 3 1 2 1 2 1 2

Output

5

Note

In the second example: Graphs for pairs $$$(1, 1)$$$, $$$(2, 2)$$$ and $$$(3, 3)$$$ are deserts because they don't have any cycles. Graphs for pairs $$$(1, 2)$$$ and $$$(2, 3)$$$ have one cycle of length 2 so they are deserts.

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/26/2024 09:25:00 (k3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|