Problem Description

Define a graph as a “sea urchin” if it satisfies all of the following conditions:

1. It is a connected graph.
2. It contains exactly one simple cycle.
3. For every vertex not on the cycle, its degree is at most $2$.

There is a graph with $n$ vertices and $n$ edges. The $i$-th edge connects $u_i$ and $v_i$ (the graph is not guaranteed to be connected).

Define the interval subgraph $[l,r]$ of a graph as $(V',E')$, where $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\}$. That is, this interval subgraph contains exactly the edges in the interval and all vertices that appear in at least one edge in the interval.

Now there are $q$ queries. Each query gives an interval $l,r$. For this $l,r$, compute how many sub-intervals $[l',r']\ (l\leq l'\leq r'\leq r)$ satisfy that the interval subgraph $[l',r']$ of the original graph is a sea urchin.

Additional notes for Condition 2:

1. A simple cycle means: you can start from any vertex, traverse some non-repeated edges, and return to the start vertex; you must traverse at least one edge; and you do not visit any repeated vertex except that the start and end vertex are the same. For example, $1-2-3-1$ is a simple cycle. Two parallel edges $1-2$ also form a simple cycle. But a graph with only one vertex is not. Also, $1-2-3-4-5-3-1$ is not a simple cycle. (Here the cycle is written as a path starting from some vertex.)
2. Condition $2$ also requires that, besides the cycle edges, there is no edge whose both endpoints are on this cycle.

Input Format

The first line contains an integer $n$, meaning the number of vertices and the number of edges.

The next $n$ lines each contain two integers $u_i,v_i$, describing an edge.

The next line contains an integer $q$.

The next $q$ lines each contain two integers $l,r$, describing a query.

Output Format

Output $q$ lines, each containing one number, the answer to the corresponding query.

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

Hint

Idea: lk&nzhtl1477, Solution: lk&ccz181078, Code: lk&ccz181078, Data: lk&ccz181078.

The testdata guarantees that there are no self-loops.

Translated by ChatGPT 5