← 返回题目列表

AtCoder · pakencamp_2021_day3_g

G. 旅人画题3

中文机器翻译题面 查看原题

配点 : 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
  • 所有输入均为整数

小課題

  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 点)无附加约束

入力

输入将以以下形式从标准输入给出。

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 约束。

原案: 企鹅人