题目描述

定义一个图为海胆，如果它满足以下条件：

1. 是一个连通图
2. 包含恰好一个简单环
3. 除了环以外的点每个点度数不超过 $2$

有一张图，有 $n$ 个点，$n$ 条边，第 $i$ 条边连接 $u_i$ 和 $v_i$（不保证联通）。

定义一张图的区间子图 $[l,r]$ 为 $(V',E')$，其中：

• $E'=\{(u_i,v_i) \mid l\leq i\leq r\}$
• $V'=\{u_i \mid l\leq i\leq r\} \cup \{v_i \mid l\leq i\leq r\}$

也就是说，这个区间子图包含且仅包含区间中的边和所有在区间中一条边上的点。

现在有 $q$ 次询问，每次给定一个区间 $[l,r]$，求 $[l,r]$ 有多少个子区间 $[l',r']$（满足 $l\leq l'\leq r'\leq r$）满足原图的 $[l',r']$ 区间子图是个海胆。

对于条件 2 的补充说明：

简单环的定义是：可以从任一点开始经过一些不重复的边回到起点，途中经过了至少一条边，且除了起点和终点相同以外不经过重复点。例如：

• $1\text{-}2\text{-}3\text{-}1$ 是简单环
• 两条 $1\text{-}2$ 的边是简单环
• 但只有一个点的时候不是
• $1\text{-}2\text{-}3\text{-}4\text{-}5\text{-}3\text{-}1$ 也不是

（这里的环用某一个点开始的路径表示）

条件 2 要求除了环边以外不存在边两端都在这个环上。

输入格式

第一行一个整数 $n$，表示点数和边数。

接下来 $n$ 行，每行两个整数 $u_i,v_i$ 表示一条边。

接下来一行一个整数 $q$。

接下来 $q$ 行，每行两个整数 $l,r$ 表示一个询问。

输出格式

$q$ 行，每行一个数表示这组询问的答案。

样例

输入

10
1 3
3 4
1 2
5 2
5 6
2 6
3 4
2 9
2 1
3 1
5
1 10
9 10
3 10
1 7
4 9

输出

4
0
3
3
1

好的，我看到原表格了。我来重新整理这个表格，保持原内容但修正格式：

---

我看到表格确实还有问题。让我根据题目逻辑来完整修正这个表格：

---

数据范围与提示

数据保证不存在自环。

子任务编号	$n \leq$	$q \leq$	特殊性质	分值
1	$100$		无	$5$
2	$500$			$15$
3	$5000$
4	$50000$
5	$10^6$	$1$
6		$10^6$	原图是一个海胆
7			无	$20$

---