配点 : 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 约束。
原案: 企鹅人