Problems
Special graph
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 contains a natural number n (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 vertex i. Third line contains a natural number m (m ≤ 105
) - 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.
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