小R与手机

Time Limit: 8000/4000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

Description

小R有n部手机,为了便于管理,他对一些手机设置了“呼叫转移”的功能。
具体来说,第i ( 1 <= i <= n )部手机有个参数 $a_i ( 0 <= a_i <= n, a_i \neq $ i )。若 $a_i$ $\neq$ 0 则表示第i部手机接到电话时会将电话无条件转移给第 $a_i $部手机(此时如果 $a_{a_i} \neq 0 $, 会继续进行呼叫转移)。
如果一部手机接到电话会导致至少 $10^9 $次呼叫转移,则这次电话无法接通。
现在有m个事件依次发生,具体如下:
$\bullet $1 x y表示将第x部手机的参数设置为y,即将 $a_x$设置为y ;
$\bullet $2 x表示询问给第x部手机打电话,最终接到电话的手机编号(如果无法接通, 则编号为-1 )。
小R当然知道怎么做啦!但是他想考考你。

Input

只包含一组测试数据。
输入的第一行有两个整数n, m。保证1 <= n, m <= 2 * $10^5 $。
接下来一行,包含n个整数,第i个整数为 $a_i $。
接下来m行,每一行为一个事件,具体格式见问题描述。
对于事件1,保证1 <= x <= n, 0 <= y <= n, x $\neq$ y ;对于事件2,保证1 <= x <= n

Output

对每个询问事件输出一行一个整数,表示最终接到电话的手机编号,如果无法接 通,输出-1。

Sample Input

5 6 2 3 4 5 0 2 2 2 5 1 4 3 2 1 1 4 0 2 1

Sample Output

5 5 -1 4

Hint

jiangzijing2015

Source

2016年中国大学生程序设计竞赛(合肥)-重现赛(感谢安徽大学)

提交代码