시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 64 MB | 15 | 9 | 9 | 64.286% |
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:
First line of input contains a natural number 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 vertexi.
Third line contains a natural number M ≤ 105 - the number of queries.
The following M contain a query each. Queries are given in the manner described above.
On the i-th line output the answer for the i-th query of type 2 a b.
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 2 1 3
4 2 -1 -1 -1
4 4 4 1 3 5 2 2 4 2 2 1 1 4 1 2 2 3 1
1 3 1