COCI '10 Contest 7 #5 Kuglice

View as PDF

Submit solution


Points: 12 (partial)
Time limit: 1.0s
Memory limit: 32M

Problem types

Mirko and Slavko love playing with marbles. On an exciting Friday, Mirko has come up with a marble game which he wants to show to Slavko.

In the game, Mirko constructs a directional graph in which all vertices have at most one outgoing edge. Then he places a marble on one of the vertices. Whenever a marble is on some vertex X, the marble moves to the adjacent vertex connected by a single edge, if such exists. The movement of the marble continues until a vertex with no outgoing edge is visited, where the marble stops. It is also possible that the marble traverses the graph indefinitely in case no such vertex is ever visited.

To make sure that Slavko understands the rules of the game, Mirko will ask a series of queries. The types of queries are as follows:

1 X – unless the marble gets stuck in a loop, on which vertex will the marble stop if it is placed on the vertex X?

2 X – delete the outgoing edge of the vertex X (it is guaranteed that such edge will always exist).

Note: queries are executed in order and are cumulative (one affects another).

Input Specification

The first line contains a positive integer N (1 \le N \le 300\,000), the number of vertices in the graph.

The second line contains exactly N positive integers separated by a single space, where the number at position i denotes the index of the destination of the outgoing edge from vertex with index i. The zero value represents that there is no outgoing edge from the vertex with index i.

The following line contains a single positive integer Q (1 \le Q \le 300\,000), the number of queries.

The remaining Q lines contain queries in the format described above.

Output Specification

For each query of type 1, output the index of the vertex where the marble stops, one per line, in the order of the execution of queries. If the marble never stops, output CIKLUS instead.

Sample Input 1

3
2 3 1
7
1 1
1 2
2 1
1 2
1 1
2 2
1 2

Sample Output 1

CIKLUS
CIKLUS
1
1
2

Sample Input 2

5
0 3 5 3 4
6
1 1
1 2
2 4
1 2
2 3
1 2

Sample Output 2

1
CIKLUS
4
3

Comments

There are no comments at the moment.