Description

你有一个凸多边形。多边形的顶点按顺序从 $1$ 到 $n$ 编号。你还有这个多边形的一个三角剖分，给出为 $n-3$ 条对角线的列表。

你还会得到 $q$ 个查询。每个查询由两个顶点索引组成。对于每个查询，找到这两个顶点之间的最短距离，前提是你可以通过多边形的边和给定的对角线移动，距离以你经过的边和对角线的总数来衡量。

Input Format

输入文件的第一行包含一个整数 $n$ —— 多边形的顶点数 $(4 \le n \le 50 000)$。

接下来的 $n-3$ 行中的每一行包含两个整数 $a_{i}, b_{i}$ —— 第 $i$ 条对角线的两个端点 $(1 \le a_{i}, b_{i} \le n , a_{i} \neq b_{i})$。

下一行包含一个整数 $q$ —— 查询的数量 $(1 \le q \le 100 000)$。

接下来的 $q$ 行中的每一行包含两个整数 $x_{i}, y_{i}$ —— 第 $i$ 个查询中的顶点 $(1 \le x_{i}, y_{i} \le n)$。

保证没有对角线与多边形的边重合，并且没有两条对角线重合或相交。

Output Format

对于每个查询，输出一行包含最短距离。

6
1 5
2 4
5 2
5
1 3
2 5
3 4
6 3
6 6

2
1
1
3
0

Hint

时间限制：2 秒，内存限制：256 MB。

题面翻译由 ChatGPT-4o 提供。