Distance on Triangulation#7564
Given a regular polygon with vertices. The vertices of the polygon are numbered consecutively from to . A triangulation of this polygon is also given in the form of a list of n - 3 diagonals.
There are queries. Each query is specified by the numbers of two vertices. For each query, you need to determine the shortest distance between these two vertices, moving along the sides or the given diagonals of the polygon. The distance is defined as the total number of sides and diagonals traversed.
The first line contains an integer n~(4 \le n \le 50000) — the number of vertices of the polygon.
The next n - 3 lines each contain two integers a_i, b_i~(1 \le a_i, b_i \le n, a_i \ne b_i) — the endpoints of the -th diagonal.
The next line contains an integer q~(1 \le q \le 10^5) — the number of queries.
The next lines contain two integers x_i, y_i~(1 \le x_i, y_i \le n) — the vertices of the -th query.
It is guaranteed that:
no diagonal coincides with a side of the polygon;
no two diagonals coincide or intersect.
For each query, print one integer on a separate line — the shortest distance between the given vertices.
Example 1