Shortest Path in a Triangulated Convex Polygon

You are given a convex polygon with n vertices numbered from 1 to n. The polygon is triangulated by n − 3 diagonals. In addition to the diagonals, the polygon has its boundary edges connecting consecutive vertices (with vertex n connected back to vertex 1).

You are also given q queries. Each query contains two vertex indices. For every query, determine the shortest distance (in terms of the number of edges traversed) between the two vertices if you can travel using both the sides of the polygon and the provided diagonals.

The shortest distance is the minimum number of edges (sides or diagonals) that must be crossed to go from one vertex to the other.

Note: All formulas are given in LaTeX format. For example, the vertices are numbered from $1$ to $n$ and the number of diagonals is $n-3$.

inputFormat

The input is given in the following format:

 n
 (n-3 lines, each containing two integers u and v representing a diagonal)
 q
 (q lines, each containing two integers s and t, the endpoints of a query)

Explanation:

• The first line contains the integer n, the number of vertices in the polygon.
• The next n-3 lines each contain two integers $u$ and $v$ representing a diagonal connecting vertices $u$ and $v$.
• The following line contains the integer q, the number of queries.
• Each of the next q lines contains two integers $s$ and $t$ specifying a query asking for the shortest path from vertex $s$ to vertex $t$.

outputFormat

For each query, output a single line containing one integer, the minimum number of sides/diagonals required to go from the starting vertex to the ending vertex.

sample

4
1 3
3
1 2
1 3
2 4

1
1
2