선분 친구 (큰 버전)

수직선 위에 $N$개의 선분이 살고 있다. 두 선분은 공통으로 가지는 점이 하나라도 있을 때만 대화할 수 있어서, 그런 두 선분끼리만 친구가 되었다. 끝점 하나만 맞닿아도 공통점이 있는 것으로 본다.

위 그림에서 브라운과 코니는 친구가 되었고 문과 제임스도 친구가 되었지만, 브라운과 샐리는 친구가 되지 못했다.

선분들은 자신들이 얼마나 가까운 사이인지 확인해보려고 한다. 문과 레너드는 친구가 아니지만 제임스가 문, 레너드와 모두 친하므로 문은 레너드의 친구의 친구다. 비슷하게 브라운은 샐리의 친구의 친구의 친구의 친구다. 친구 사이를 1만큼 가깝다고 하면, 문과 레너드는 2만큼 가깝고 브라운과 샐리는 4만큼 가깝다. 문은 코니의 친구의 친구이기도 하지만 코니의 친구이기도 하므로, 문과 코니는 1만큼 가깝다.

선분 마을의 시장인 당신은 두 선분이 "우리가 얼마나 가까운 사이야?"라고 물어볼 때마다 바로 답해야 한다. 즉 질문으로 주어진 두 선분 $A$, $B$에 대해 $A$에서 친구 관계를 따라 $B$까지 가는 데 필요한 최소 횟수를 구하는 프로그램을 작성하라.

첫째 줄에 선분의 수 $N$이 주어진다. ($2 \le N \le 150000$)

다음 $N$개의 줄에는 1번부터 $N$번까지 각 선분의 왼쪽 끝 좌표 $L_i$와 오른쪽 끝 좌표 $R_i$가 공백을 사이에 두고 주어진다. ($-1000000 \le L_i \le R_i \le 1000000$)

그다음 줄에 질문의 수 $Q$가 주어진다. ($1 \le Q \le 150000$)

마지막 $Q$개의 줄에는 질문하는 두 선분의 번호 $A$와 $B$가 주어진다. ($1 \le A, B \le N$, $A \ne B$)

질문마다 한 줄에 두 선분이 가까운 정도를 출력한다. 친구 관계를 아무리 따라가도 두 선분이 이어지지 않으면 -1을 출력한다.