특수한 그래프 Batch 컴파일 명령

여러분 앞에 $N$개의 정점을 가진 그래프가 놓여 있습니다. 승현이는 이 그래프가 특별하다고 주장하는데, 각 정점의 외향 차수가 최대 1이기 때문입니다. 승현이는 아래 형태의 질의들을 해결하고자 합니다.

• $1$ $a$ - 정점 $a$의 유일한 외향 간선을 지웁니다. 지울 간선이 존재한다는 것은 보장됩니다. $1 \le a \le N.$
• $2$ $a$ $b$ - 정점 $a$에서 정점 $b$까지 가는 경로가 존재한다면 최단 경로의 길이를 출력하고, 존재하지 않는다면 -1을 출력합니다. $1 \le a,b \le N.$

입력 형식

첫 번째 줄에 정점의 수 $N$ ($1 \le N \le 10^5$)이 주어집니다.

그 다음 줄에는 $N$개의 정수가 주어집니다. 이 중 $i$번째 정수는 $next_{i}$ ($0 \le next_{i} \le N$)인데, 정점 $i$에서 정점 $next_{i}$로 가는 단방향 간선이 존재한다는 것입니다. 단 $next_{i} = 0$이라면 $i$번 정점의 외향 간선은 없습니다.

세 번째 줄에는 질의의 수 $M$ ($1 \le M \le 10^5$)이 주어집니다.

다음 $M$개 줄에는 질의가 주어집니다. 질의의 형태는 위에서 명시한 대로 주어지며, 각 정수 사이에는 공백이 하나씩 주어집니다.

출력 형식

$i$번째 줄에 $i$번째 2번 형태 쿼리의 답을 출력합니다.

입력과 출력의 예

참고

50%의 테스트 케이스에 대해 $1 \le N \le 2 \times 10^{3}, M \le 2 \times 10^{4}.$