e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more
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