P6976 [NEERC 2015] Distance on Triangulation

你有一个凸多边形。多边形的顶点按顺序从 $1$ 到 $n$ 编号。你还有这个多边形的一个三角剖分，给出为 $n-3$ 条对角线的列表。 你还会得到 $q$ 个查询。每个查询由两个顶点索引组成。对于每个查询，找到这两个顶点之间的最短距离，前提是你可以通过多边形的边和给定的对角线移动，距离以你经过的边和对角线的总数来衡量。

输入文件的第一行包含一个整数 $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)$。 保证没有对角线与多边形的边重合，并且没有两条对角线重合或相交。

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

时间限制：2 秒，内存限制：256 MB。 题面翻译由 ChatGPT-4o 提供。