You 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.
Output
The output contains one integer number – the answer.
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.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 6
1 2
2 3
3 4
4 5
5 1
2 4
|
20
|
|
2
|
2 3
1 2
1 2
1 2
|
5
|