Sea Urchin

We are given an undirected graph with (n) vertices and (n) edges. The (i)-th edge connects vertices (u_i) and (v_i) (the graph is not guaranteed to be connected). We define an interval subgraph ([l,r]) as the graph ((V',E')) where (E' = { (u_i,v_i) \mid l \le i \le r }) and (V' = {u_i,v_i \mid l \le i \le r}).

A graph is called a sea urchin if it satisfies the following conditions:

1. It is connected.
2. It contains exactly one simple cycle. (A simple cycle is defined as a path which starts at some vertex, goes through a sequence of edges without repeating any edge or vertex (except that the starting and ending vertex coincide) and contains at least one edge. For example, (1-2-3-1) is a simple cycle. Note that two edges both connecting (1) and (2) count as a simple cycle, but a single vertex does not form a cycle. Also, (1-2-3-4-5-3-1) is not a simple cycle.) Moreover, the condition requires that aside from the cycle edges there is no extra edge with both endpoints on the cycle.
3. For every vertex that is not on the cycle, its degree in the subgraph is at most (2).

You are given (q) queries. Each query provides an interval (l,r) (with (1 \le l \le r \le n)). For each query, count the number of subintervals ([l',r']) with (l \le l' \le r' \le r) such that the interval subgraph ([l', r']) is a sea urchin.

Note: The sea urchin is essentially a connected unicyclic graph (i.e. a connected graph with (#edges = #vertices)) satisfying the additional restriction on the degrees of vertices not lying on the unique cycle.

inputFormat

The first line contains a single integer (n) (the number of vertices and edges). The next (n) lines each contain two integers (u_i) and (v_i), indicating an undirected edge between vertices (u_i) and (v_i). The next line contains a single integer (q) denoting the number of queries. Each of the following (q) lines contains two integers (l) and (r) describing a query.

outputFormat

For each query, output one line containing a single integer, the number of subintervals ([l',r']) (with (l \le l' \le r' \le r)) for which the corresponding interval subgraph is a sea urchin.

sample

3
1 2
2 3
3 1
1
1 3

1