P6706 [COCI 2010/2011 #7] KUGLICE

Mirko and Slavko like playing marbles. On an exciting Friday, Mirko invented a marble game and wanted to show it to Slavko. In the game, Mirko builds a directed graph where each vertex has outdegree at most $1$. Then he places a marble on one vertex. As long as the marble is at some vertex $X$, it moves to the adjacent vertex connected by the outgoing edge (if there is no such edge, it stays). The marble keeps moving until it reaches a vertex with outdegree $0$. It is also possible that the marble travels around the graph forever because there is no vertex with outdegree $0$. To make sure Slavko understands the rules, Mirko asks a series of queries. The query types are: 1. `1 X`: Unless the marble gets stuck in a cycle, find the index of the final stopping vertex after placing the marble at $X$. 2. `2 X`: Delete the outgoing edge of vertex $X$. (It is guaranteed to exist.) Note that the queries are ordered.

You are given a directed graph where each vertex has outdegree $0$ or $1$. There are the following queries: 1. `1 X`: Given the marble start vertex $X$, find where the marble stops. 2. `2 X`: Delete the outgoing edge of vertex $X$. (It is guaranteed to exist.) Marble movement rules: Starting from the initial vertex, follow outgoing edges until reaching a vertex whose outdegree is $0$.

The first line contains a positive integer $n$, the number of vertices in the graph. The second line contains $n$ positive integers. The $i$-th number is the index of the vertex that the outgoing edge of $i$ points to; if it is $0$, then the edge does not exist. The next line contains a positive integer $Q$, the number of queries. The next $Q$ lines each contain one query in one of the formats above.

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

#### Constraints For $100\%$ of the testdata, $1 \le n,Q \le 3 \times 10^5$. #### Notes This problem is worth $120$ points. Translated from [COCI2010-2011](https://hsin.hr/coci/archive/2010_2011/) [CONTEST #7](https://hsin.hr/coci/archive/2010_2011/contest7_tasks.pdf) T5 KUGLICE。 Translated by ChatGPT 5