AT_pakencamp_2021_day3_g 旅人計画問題3

[problemUrl]: https://atcoder.jp/contests/pakencamp-2021-day3/tasks/pakencamp_2021_day3_g パ研王国は $ 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 $ を経由することは可能です。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ u_1 $ $ v_1 $ $ u_2 $ $ v_2 $ $ \hspace{0.45cm}\vdots $ $ u_M $ $ v_M $

答えを出力せよ。

### 制約 - $ 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)