시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 64 MB159964.286%

문제

You are given a directed graph with N vertices. The special thing about the graph is that each vertex has at most one outgoing edge. Your task is to answer the following two types of queries:

  • 1 a - delete the only edge outgoing from vertex a. It is guaranteed that the edge exists. 1 ≤ a ≤ N
  • 2 a b - output the length of the shortest path from vertex a to vertex b, if the path exists. Otherwise output "-1" without quotes. 1 ≤ a, b ≤ N

입력

First line of input contains a natural number N ≤ 105 - the number of vertices in the graph.

The following line contains N integer numbers, i-th number is nexti (0 ≤ nexti ≤ N), meaning that there is an edge from vertex i to vertex nexti. If nexti = 0, assume that there is no outgoing edge from vertexi.

Third line contains a natural number M ≤ 105 - the number of queries.

The following M contain a query each. Queries are given in the manner described above.

출력

On the i-th line output the answer for the i-th query of type 2 a b.

예제 입력 1

6
3 3 4 5 6 4
6
2 1 6
2 1 4
2 1 2
1 3
2 1 6
2 1 4
2 1 3

예제 출력 1

4
2
-1
-1
-1

예제 입력 2

4
4 4 1 3
5
2 2 4
2 2 1
1 4
1 2
2 3 1

예제 출력 2

1
3
1