Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение 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