커플 만나기

Nlogonia의 항공 규정에 따르면 모든 도시는 다른 한 도시로 향하는 출발 항공편을 정확히 하나 등록해야 한다. 항공편은 등록된 방향으로만 이용할 수 있다. 즉, 도시 $X$에서 도시 $Y$로 가는 항공편이 등록되어 있어도 $Y$에서 $X$로 가는 항공편이 있다는 뜻은 아니다. 모든 도시가 출발 항공편을 정확히 하나 등록하므로, 등록된 항공편의 총 수는 도시의 수와 같다.

커플 매칭 협회는 두 사람이 만나기 위해 타야 하는 항공편 수의 최솟값을 계산해 주는 서비스를 운영한다. 두 사람은 둘 다 살지 않는 도시에서 만나도 된다. 두 사람이 각각 도시 $A$와 도시 $B$에서 출발한다고 할 때, 서비스는 $A$와 $B$ 양쪽에서 항공편으로 도달할 수 있는 도시 $C$ 중에서 $A$에서 $C$까지 필요한 항공편 수와 $B$에서 $C$까지 필요한 항공편 수의 합이 최소가 되는 $C$를 찾는다. 도시 $C$는 $A$, $B$ 또는 둘 다와 같을 수도 있다.

등록된 모든 항공편의 목록과 여러 개의 질의가 주어진다. 각 질의는 한 커플이 사는 두 도시를 나타낸다. 각 질의에 대해 두 사람이 만나기 위해 필요한 항공편 수의 최솟값을 구하라.

입력은 여러 개의 테스트 케이스로 이루어지며 파일의 끝에서 종료된다.

각 테스트 케이스는 여러 줄로 주어진다.

• 첫째 줄에는 도시의 수를 나타내는 정수 $N$이 주어진다 ($2 \le N \le 10^5$). 도시는 $1$부터 $N$까지 번호가 매겨져 있다.
• 둘째 줄에는 $N$개의 정수 $F_1, F_2, \ldots, F_N$이 주어진다. $F_i$는 도시 $i$에서 등록된 유일한 출발 항공편이 향하는 도시를 뜻한다 ($1 \le F_i \le N$, $F_i \ne i$).
• 셋째 줄에는 질의의 수를 나타내는 정수 $Q$가 주어진다 ($1 \le Q \le 10^5$).
• 이어지는 $Q$개의 줄에는 각각 한 커플이 사는 두 도시를 나타내는 정수 $A$와 $B$가 주어진다 ($1 \le A, B \le N$).

한 테스트 케이스 안에서, 어떤 도시 $X$에서 어떤 도시 $Y$로 항공편으로 이동할 수 있다면 그때 필요한 항공편 수는 최대 $10^4$이다.

각 질의마다 한 줄씩 출력한다. 커플이 항공편으로 만날 수 있다면 만나기 위해 타야 하는 항공편 수의 최솟값을 출력하고, 결코 만날 수 없다면 $-1$을 출력한다. 모든 테스트 케이스의 답을 순서대로 출력한다.