Mirko and Slavko love playing with marbles. In the game, Mirko constructs a directed 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 the single edge, if such exists. The movement 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.

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 an edge will always exist).

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

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 the 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.

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

riseoj 작성

출처 COCI 2010/2011 Contest 7