eolymp
bolt
Try our new interface for solving problems
Problems

Distance on Triangulation

Distance on Triangulation

Time limit 1 second
Memory limit 128 MiB

You have a convex polygon. The vertices of the polygon are successively numbered from 1 to n. You also have a triangulation of this polygon, given as a list of n3 diagonals.

You are also given q queries. Each query consists of two vertex indices. For each query, find the shortest distance between these two vertices, provided that you can move by the sides and by the given diagonals of the polygon, and the distance is measured as the total number of sides and diagonals you have traversed.

Input data

The first line contains an integer n (4n50 000) - the number of vertices of the polygon.

Each of the following n3 lines contains two integers a[i], b[i] - the ends of the i-th diagonal (1a[i], b[i]n, a[i]b[i]).

The next line contains an integer q (1q100 000) - the number of queries.

Each of the following q lines contains two integers x[i], y[i] - the vertices in the i-th query (1x[i], y[i]n). It is guaranteed that no diagonal coincides with a side of the polygon, and that no two diagonals coincide or intersect.

Output data

For each query output a line containing the shortest distance.

prb7564.gif

Examples

Input example #1
6
1 5
2 4
5 2
5
1 3
2 5
3 4
6 3
6 6
Output example #1
2
1
1
3
0
Source 2015 ACM NEERC, Semifinals, December 6, Problem D