問題文

パ研王国は 1 から N までの番号が付けられた N 個の都市と、1 から M までの番号が付けられた M 本の道路からなります。各 i\ (1 \leq i \leq M) について、辺 i は都市 u_i と都市 v_i を双方向に結んでいます。

ペンギンくんは今、パ研王国の中を旅行する計画を立てています。彼はその計画を立てるにあたって、以下の情報を知りたがっています。

• 1 \leq l \leq r \leq M を満たす整数対 (l,r) であって、以下の条件を満たすものはいくつあるか。
  • ある都市 X を出発し、道路 l、道路 l+1、\cdots、道路 r を好きな順番でちょうど一度ずつ通って都市 X に戻るような経路が存在する。

この値を求めることは、ペンギンくんには難しすぎました。そのため、彼の代わりに答えを求めてあげてください。

（16:30 補足：）

• 経路において道路 l、道路 l+1、\cdots、道路 r 以外の道路を通ることはできません。
• 経路の途中で都市 X を経由することは可能です。

制約

• 1 \leq N,M \leq 5 \times 10^4
• 1 \leq u_i,v_i \leq N
• u_i \neq v_i
• 入力は全て整数

小課題

1. (200 点) N,M \leq 3000
2. (150 点) v_i = u_{i+1}\ (1 \leq i \leq M-1)
3. (350 点) M は偶数、(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 点) 追加の制約はない

入力例 1

4 4
1 2
2 3
3 4
2 4

出力例 1

1

問題文中の条件を満たす (l,r) は、(2,4) の 1 つのみです。

(l,r)=(2,4) においては、例えば都市 2 を出発したあと道路 4、道路 3、道路 2 をこの順に通って都市 2 に戻ってくるような経路が存在します。

この入力は小課題 1,4 の制約を満たします。

入力例 2

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

出力例 2

3

この入力は小課題 1,4 の制約を満たします。

入力例 3

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

出力例 3

6

この入力は小課題 1,2,4 の制約を満たします。

入力例 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

出力例 4

18

この入力は小課題 1,3,4 の制約を満たします。

原案: penguinman