Distance on Triangulation

You have a convex polygon. Its vertices are numbered from 1 to $n$ in order around the boundary. You also have a triangulation of this polygon, given as $n-3$ diagonals that do not cross each other.

You are given $q$ queries. Each query consists of two vertex numbers. Moving only along the sides of the polygon and along the given diagonals, find the shortest distance between the two vertices of the query. The distance is the number of sides and diagonals you traverse.

The first line contains an integer $n$, the number of vertices of the polygon ($4 \le n \le 50000$).

Each of the next $n-3$ lines contains two integers $a_i$ and $b_i$, the endpoints of the $i$-th diagonal ($1 \le a_i, b_i \le n$, $a_i \ne b_i$).

The next line contains an integer $q$, the number of queries ($1 \le q \le 100000$).

Each of the next $q$ lines contains two integers $x_i$ and $y_i$, the two vertices of the $i$-th query ($1 \le x_i, y_i \le n$).

No diagonal coincides with a side of the polygon, and no two diagonals coincide or cross.

For each query print the shortest distance on its own line.

The picture shows the polygon and the triangulation of the first example.