삼각분할 위의 거리

볼록다각형이 하나 있다. 꼭짓점에는 둘레를 따라 1번부터 $n$번까지 차례로 번호가 붙어 있다. 이 다각형의 삼각분할도 함께 주어지며, 삼각분할은 서로 교차하지 않는 대각선 $n-3$개로 이루어진다.

질의가 $q$개 주어진다. 각 질의는 꼭짓점 번호 두 개로 이루어진다. 다각형의 변과 주어진 대각선을 따라서만 이동할 수 있을 때, 질의로 주어진 두 꼭짓점 사이의 최단 거리를 구한다. 거리는 지나간 변과 대각선의 개수이다.

첫째 줄에 다각형의 꼭짓점 개수 $n$이 주어진다. ($4 \le n \le 50000$)

다음 $n-3$개 줄에는 각각 두 정수 $a_i$, $b_i$가 주어진다. $i$번째 대각선의 두 끝점이다. ($1 \le a_i, b_i \le n$, $a_i \ne b_i$)

다음 줄에 질의의 개수 $q$가 주어진다. ($1 \le q \le 100000$)

이어지는 $q$개 줄에는 각각 두 정수 $x_i$, $y_i$가 주어진다. $i$번째 질의의 두 꼭짓점이다. ($1 \le x_i, y_i \le n$)

어떤 대각선도 다각형의 변과 일치하지 않으며, 두 대각선이 서로 같거나 교차하는 경우도 없다.

각 질의마다 최단 거리를 한 줄에 하나씩 출력한다.

그림은 첫 번째 예제에 주어진 다각형과 삼각분할이다.