AT_pakencamp_2021_day3_g 旅人計画問題3

有一张 $n$ 点（编号 $1$ 到 $n$）$m$ 边的无向图。第 $i$ 条边连接点 $u_i$ 和 $v_i$。 选定两个满足 $1 \le l \le r \le m$ 的整数 $l$ 和 $r$，使得从某个点 $x$ 出发，按照某种顺序走完第 $l,l+1,...,r$ 条边各一次后能够回到点 $x$。（不能经过其他边；中途可以访问点 $x$） 请求出满足条件的整数对 $(l,r)$ 的数量。

第一行两个数 $n,m$。 接下来 $m$ 行，每行两个整数 $u_i,v_i$。

一行一个整数，答案。 ### 数据规模与约定 - $1 \le n,m \le 5 \times 10^4$； - $1 \le u_i,v_i \le n$，且 $u_i \neq v_i$； - 输入均为整数。

### 制約 - $ 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 $ 点) 追加の制約はない ### Sample Explanation 1 問題文中の条件を満たす $ (l,r) $ は、$ (2,4) $ の $ 1 $ つのみです。 $ (l,r)=(2,4) $ においては、例えば都市 $ 2 $ を出発したあと道路 $ 4 $、道路 $ 3 $、道路 $ 2 $ をこの順に通って都市 $ 2 $ に戻ってくるような経路が存在します。 この入力は小課題 $ 1,4 $ の制約を満たします。 ### Sample Explanation 2 この入力は小課題 $ 1,4 $ の制約を満たします。 ### Sample Explanation 3 この入力は小課題 $ 1,2,4 $ の制約を満たします。 ### Sample Explanation 4 この入力は小課題 $ 1,3,4 $ の制約を満たします。 原案: \[penguinman\](https://atcoder.jp/users/penguinman)