问题 1109. -- 游戏

1109: 游戏

时间限制: 3 Sec  内存限制: 128 MB
提交: 54  解决: 21
[提交][状态][讨论版]

题目描述

MirkoSlavko爱玩弹球戏。在一个令人激动的星期五,Mirko和Slavko玩了一把弹球游戏。Mirko构建一个有向图,所有顶点最多有1条出边。弹球从1个顶点出发可以沿着一条边移动到它的邻接点,只要它存在,而且它会继续移动到后者的邻接点去,直到最后到达一个找不到出边的顶点才停下来。如果不存在这样的点,弹球可能无限运动下去。

为了确信Slavko理解游戏的规则,Mirko将发起一系列询问,询问的类型如下:

1 X :除非弹球陷入循环,弹球从X出发,最终将在哪个点停下来。

2 X:删除X的出边(保证该边总是存在)

注意:询问是按顺序执行的。

输入

第一行包含一个正整数N(1<=N<=300000),表示图的定点数。

第二行包含由空格隔开N个正整数,第i个数表示从i顶点可以通过出边到达的定点编号。0表示该点没有出边。

接下来的一行包含1个整数Q(1<=Q<=300000),表示询问的次数。格式如上所示。

输出

对于第1类询问,输出弹球停止时所在顶点编号,每行1个,按照查询的顺序输出。如果弹球无法停止,则输出CIKLUS.


样例输入

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

样例输出

CIKLUS
CIKLUS
1
1
2

提示

来源

[提交][状态]