题目描述

给定一个凸 $n$ 边形，以及它的三角剖分。再给定 $q$ 个询问，每个询问是一对凸多边行上的顶点 $(a,b)$，问点 $a$ 最少经过多少条边（可以是多边形上的边，也可以是剖分上的边）可以到达点 $b$。

输入格式

第一行一个整数 $n$，代表有 $n$ 个点。点 $1$，$2$，$3$，$\dots$，$n$ 在凸多边形上是顺时针排布的。
接下来 $n-3$ 行，每行两个整数 $(x,y)$，代表 $(x,y)$ 之间有一条剖分边。
接下来是一个整数 $q$，代表有 $q$ 组询问。
接下来 $q$ 行是两个整数 $(a,b)$。

输出格式

输出 $q$ 行，每行一个整数代表最少边数。

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

2
1
1
3
0

数据范围与约定

对于 $100 \%$ 的数据，$n \le 50000$，$q \le 10^5$。