printРабочее место участника

printЗадачи

1632. Marbles

Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

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 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 understand the rules of the game, Mirko will ask a series of queries. The types of queries are as follows:
`1\ X` – unless the marble stucks 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 cummulative (one affects another).
Input
The first line contains a postive integer `N` (`1\ ≤\ N\ ≤\ 300000`), 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 represent that there is no outgoing edge from the vertex with index `i`.
The following line contains a single positive integer `Q` (`1\ ≤\ Q\ ≤\ 300000`), the number of queries. The remaining `Q` lines contain queries in the format described above.
Output
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
Source: COCI 2010/2011, contest #7
loading