SPECIALG - Special Graph

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

Added by:Ikhaduri
Date:2013-01-27
Time limit:0.5s-1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Izho 2013

hide comments
2017-03-14 18:23:58
347 line...
2013-11-23 04:19:55 samfisher
@shubham Yes .. the required complexity is O( log(n)*m )
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.