e-olymp
Competitions

2013 IX Международная Жаутыковская Олимпиада Алматы, Казахстан, 16 января

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 (1an),
  • 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 (1a, bn).

Input

First line contains a natural number n (n105) - the number of vertices in the graph. The following line contains n integer numbers, i-th number is nexti (0nextin), meaning that there is an edge from vertex i to vertex nexti. If nexti = 0, assume that there is no outgoing edge from vertex i. Third line contains a natural number m (m105) - the number of queries. The following m 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.

Time limit 1 second
Memory limit 64 MiB
Input example #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
Output example #1
4
2
-1
-1
-1
Input example #2
4
4 4 1 3
5
2 2 4
2 2 1
1 4
1 2
2 3 1
Output example #2
1
3
1
Source 2013 IX Zhautykov Olympiad Almaty, Kazakhstan, January 16