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

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

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

定义一张图的区间子图$[l,r]$为$(V',E'),E'=\{(u_i,v_i)|l\leq i\leq r\},V'=\{u_i|l\leq i\leq r\} \cup \{v_i|l\leq i\leq r\}$，也就是说，这个区间子图包含且仅包含区间中的边和所有在区间中一条边上的点。

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

对于条件2的补充说明：

1. 简单环的定义是 可以从任一点开始经过一些不重复的边回到起点，途中经过了至少一条边，且除了起点和终点相同以外不经过重复点，例如1-2-3-1是简单环，两条1-2的边是简单环，但只有一个点的时候不是,1-2-3-4-5-3-1也不是,(这里的环用某一个点开始的路径表示)
2. 条件2要求除了环边以外不存在边两端都在这个环上。

输入格式

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

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

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

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

输出格式

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

样例一

input

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

output

4
0
3
3
1

限制与约定

数据保证不存在自环

时间限制：$7 \texttt{s}$

空间限制：$1024 \texttt{MB}$