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
hide comments
ztrong:
2017-03-14 18:23:58
347 line... |
|
samfisher:
2013-11-23 04:19:55
@shubham Yes .. the required complexity is O( log(n)*m ) |
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 |