题目描述
Mirko 和 Slavko 喜欢玩弹珠。 在一个激动人心的星期五,Mirko 发明了一个关于弹珠的游戏,他想向 Slavko 展示。
在游戏中,Mirko 构造了一个有向图,其中每个点出度不超过 $1$。然后他在其中一个点上放了一个弹珠,只要弹珠在某个顶点 $X$ 上,弹珠就会移动到由一条边连接的相邻顶点(没有就算了)。弹珠的运动一直持续到弹珠到达一个没有出度的点为止。弹珠也有可能因没有出度为 $0$ 的点而无限遍历图。为了确保 Slavko 能理解游戏规则,Mirko 会问一系列问题。
询问类型如下:
1. `1 X`:除非弹珠卡在一个循环,求弹珠被放在 $X$ 后最后的终止点序号。
2. `2 X`:删除顶点 $X$ 的出边。(保证存在)
注意:查询有序。
给定一个有向图,其中每个点出度为 $0$ 或 $1$。
有如下询问:
1. `1 X`:给定弹珠起始点 $X$,求弹珠运动的终止点。
2. `2 X`:删除 $X$ 点出边。(保证存在)
弹珠运动规则:
从初始点沿着出边走直到一点出度为 $0$。
输入格式
第一行一个正整数 $n$,指图中顶点数。
第二行 $n$ 个正整数,其中第 $i$ 个数表示 $i$
的出边指向点序号,若 $0$ 则指不存在。
下面一行一个正整数 $Q$,指查询数目。
下面 $Q$ 行每行包含一个上述格式的查询。
输出格式
对于每个类型 $1$ 的查询,按照顺序,每行输出弹珠停止点序号。
如果弹珠永不停止,则输出 $\texttt{CIKLUS}$。
样例输入 #1
3
2 3 1
7
1 1
1 2
2 1
1 2
1 1
2 2
1 2
样例输出 #1
CIKLUS
CIKLUS
1
1
2
样例输入 #2
5
0 3 5 3 4
6
1 1
1 2
2 4
1 2
2 3
1 2
提示
对于 $100\%$ 的数据 $1 \le n,Q \le 3 \times 10^5$。