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

Input

First line of input contains a natural number N<=10^5  the number of vertices in the graph.

The following line contains N integer numbers, i-th number is next[i] (0<= next[i]<= N), meaning that there

is an edge from vertex i to vertex next[i]. If next[i] = 0, assume that there is no outgoing edge from vertex

i.

Third line contains a natural number M<=10^5  the number of queries.

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

Output

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

Example

Input:
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
Output:
4
2
-1
-1
-1