포털

새로운 회사 Sveriges Portaltrafik는 스웨덴의 통근자들이 국내를 이동하는 방식에 혁명을 일으키고자 한다. 이 회사는 기차, 비행기, 버스 교통을 연료 효율적인 포털로 대체하기 위해 스웨덴에 포털 시스템을 구축하는 획기적인 제안을 내놓았다. 이제 정부는 이 제안을 자세히 검토하라는 임무를 받았으며, 스웨덴의 최정상급 프로그래머들에게 도움을 호소하고 있다. 바로 여기서 당신이 나설 차례이다.

당신은 포털 시스템을 분석하기 위해 그 설계도를 받았다. 포털 시스템은 국내의 여러 장소에 배치된 $N$개의 포털로 이루어진다. 각 포털 $a$에는 특정 목적지 포털 $b$이 있다. 즉, $a$에 들어갈 때마다 $b$에서 나오게 된다. $b$에 들어간다고 해서 반드시 $a$로 돌아오는 것은 아니라는 점에 유의하라. Sveriges Portaltrafiks의 새로운 발상은 여행자가 한 포털에 들어간 뒤 자신이 나온 곳의 포털에 반복해서 들어가도록 함으로써 국내를 빠르게 이동할 수 있게 하는 것이다.

이제 정부는 주어진 여러 시작 포털과 도착 포털 $a$ 및 $b$에 대해, $a$에서 $b$로 이동하려면 자신이 나온 곳의 포털에 몇 번 들어가야 하는지, 또는 그것이 가능한지조차 알고 싶어 한다. 그러한 각 질의에 대해 $a$에서 $b$로 이동하기 위해 포털에 들어가야 하는 횟수로 답해야 한다. 불가능하다면 $-1$로 답해야 한다.

정부를 도와라!

점수

당신의 풀이는 여러 테스트 케이스 그룹으로 평가된다. 한 그룹의 점수를 받으려면 그 그룹의 모든 테스트 케이스를 통과해야 한다.

그룹 | 배점 | 제한 | 기타

1 | 10 |$1 \le N \le 1\,000,\ 1 \le Q \le 1\,000$| 시작 포털과 도착 포털 사이에는 항상 경로가 존재한다.

2 | 20 |$1 \le N \le 1\,000,\ 1 \le Q \le 1\,000$|

3 | 10 |$1 \le N \le 7\,000,\ 1 \le Q \le 120\,000$| 시작 포털과 도착 포털 사이에는 항상 경로가 존재한다.

4 | 10 |$1 \le N \le 7\,000,\ 1 \le Q \le 120\,000$|

5 | 10 |$1 \le N \le 50\,000,\ 1 \le Q \le 70\,000$| 시작 포털과 도착 포털 사이에는 항상 경로가 존재한다. 테스트 케이스는 그룹 6보다도 조금 더 쉽게 구성되어 있다.

6 | 30 |$1 \le N \le 50\,000,\ 1 \le Q \le 70\,000$| 시작 포털과 도착 포털 사이에는 항상 경로가 존재한다.

7 | 10 |$1 \le N \le 50\,000,\ 1 \le Q \le 70\,000$|

입력의 첫째 줄에는 국내에 배치될 포털의 수를 나타내는 정수 $N$이 주어진다. 이어지는 $N$개의 줄에는 수 $1 \le d_i \le N$가 주어지며, 이는 $i$번째 줄의 포털이 포털 $d_i$로 이어진다는 뜻이다. 포털에는 하나부터 번호가 매겨져 있으며(가장 작은 번호는 1, 가장 큰 번호는 $N$이다), 입력에는 $1$부터 $N$까지 순서대로 주어진다.

이어서 답해야 하는 질의의 수를 나타내는 정수 $Q$이 한 줄에 주어진다. 그 뒤에는 두 정수 $1 \le s, e \le N$가 주어지는 $Q$개의 줄이 이어진다. 이 수들은 시작 포털 $s$과 도착 포털 $e$의 번호를 나타내며, 당신의 임무는 $s$에서 시작할 때 $e$에 도달하려면 포털을 몇 번 통과해야 하는지 답하는 것이다. 각 질의에 대해 $s \neq e$가 성립한다.

$Q$개의 줄을 출력해야 하며, 각 질의마다 하나의 수, 즉 주어진 시작 포털에서 도착 포털로 이동하기 위해 포털을 통과해야 하는 횟수를 출력한다. 불가능하다면 $-1$를 출력한다. 각 질의의 답을 별도의 줄에 출력한다.

예제 입력 1의 그림.

예제의 네트워크는 그림과 같다. 세 개의 질의가 주어진다. 첫 번째 질의는 $1$에서 시작하여 $2$에 도달하려 할 때 포털에 몇 번 들어가야 하는지를 묻는다. $1$에 들어가면 곧바로 $2$에 도달하므로 답은 $1$이다. $1$에서 $4$로 이동하려면 세 번의 이동이 필요하다. 마지막 질의의 답은 $-1$이다. 포털을 아무리 오래 통과하더라도 $2$에서 $5$로는 절대 이동할 수 없기 때문이다.