포털

스웨덴의 신생 기업 Sveriges Portaltrafik는 스웨덴 통근자들이 나라 안을 이동하는 방식을 바꾸려 한다. 이 회사는 기차, 비행기, 버스를 대체할 연료 효율이 좋은 포털 시스템을 스웨덴에 구축하자고 제안했다. 정부는 이 제안을 자세히 검토하도록 지시받았고, 스웨덴의 엘리트 프로그래머들에게 도움을 요청했다. 당신이 그 역할을 맡는다.

포털 시스템은 나라 곳곳에 배치된 $N$개의 포털로 이루어져 있다. 각 포털 $a$에는 목적지 포털 $b$가 정해져 있다. 즉, $a$에 들어갈 때마다 $b$에서 나오게 된다. $b$에 들어간다고 해서 반드시 $a$로 돌아오는 것은 아니다.

정부는 주어진 시작 포털 $a$와 도착 포털 $b$마다, $a$에서 $b$까지 가려면 나온 포털에 몇 번 다시 들어가야 하는지 알고 싶어 한다. 가능하지 않다면 그 사실도 알아야 한다. 각 질의에 대해 $a$에서 $b$까지 가는 데 필요한 횟수를 답하라. 불가능하면 $-1$을 답하라.

첫 줄에 포털의 개수 $N$이 주어진다. 다음 $N$개의 줄에는 각각 정수 $1 \le d_i \le N$이 주어지며, 이는 $i$번 포털이 $d_i$번 포털로 연결된다는 뜻이다. 포털은 1번부터 $N$번까지 번호가 매겨져 있고, 입력에도 그 순서대로 나온다.

다음 줄에는 질의의 개수 $Q$가 주어진다. 이어서 $Q$개의 줄에 시작 포털 $s$와 도착 포털 $e$를 나타내는 두 정수 $1 \le s, e \le N$이 주어진다. 모든 질의에서 $s \neq e$이다.

$Q$개의 줄에 질의마다 하나씩 답을 출력한다. 답은 시작 포털에서 출발해 도착 포털에 닿기까지 포털을 통과해야 하는 횟수이다. 불가능하면 $-1$을 출력한다. 각 답은 별도의 줄에 쓴다.

$1 \le N \le 50\,000$

$1 \le Q \le 70\,000$

그림은 예제 입력 1의 네트워크를 보여준다. 질의는 세 개다. 첫 번째 질의는 1에서 출발해 2에 도달하려면 포털에 몇 번 들어가야 하는지 묻는다. 1에 들어가면 바로 2에서 나오므로 답은 1이다. 1에서 4까지는 세 번 이동해야 한다. 마지막 질의의 답은 $-1$이다. 2에서 출발하면 포털을 아무리 많이 통과해도 5에 도달할 수 없기 때문이다.