G - 旅人計画問題3
Editorial
/
Time Limit: 4 sec / Memory Limit: 1024 MB
配点 : 800 点
問題文
パ研王国は 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
- 入力は全て整数
小課題
- (200 点) N,M \leq 3000
- (150 点) v_i = u_{i+1}\ (1 \leq i \leq M-1)
- (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)
- (100 点) 追加の制約はない
入力
入力は以下の形式で標準入力から与えられる。
N M u_1 v_1 u_2 v_2 \hspace{0.45cm}\vdots u_M v_M
出力
答えを出力せよ。
入力例 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