弹珠游戏

题目描述:

兔警官朱迪解救了所有被困的动物之后，相比于之前也没那么忙了，所以朱迪闲暇之余研究儿时的弹珠游戏。于是便邀请老朋友狐狸尼克陪她一起玩弹珠游戏。

朱迪兴致勃勃地向尼克展示改良版的弹珠游戏的玩法。

在游戏中，朱迪构造了一个包含 N 个节点的有向图，其中每个节点的出度不超过 1。然后她在其中某一个节点上放了一个弹珠，只要弹珠在某个节点 X ( 1 ≤ X ≤ N ) 上，弹珠就会移动到由一条边连接的相邻节点( 如果有的话 )。弹珠的运动一直持续到弹珠到达一个没有出度的节点为止。弹珠也有可能因没有出度为 0 的节点而无限的遍历下去。为了确保尼克能理解游戏规则，朱迪会问一系列问题，以帮助尼克更好的理解弹珠游戏。

朱迪询问类型如下：

1  X：弹珠被放在节点 X 后，最后的终止节点序号( 当然除了弹珠卡在某个地方一直循环的情况 )  

2  X：删除节点 X 的出边。( 数据保证节点 X 的出边存在 )

特别注意：查询按顺序执行。

弹珠运动规则：从初始节点沿着出边走，一直走到一个出度为 0 的节点或者卡在某个地方一直这样转下去。 

输入格式:

第一行一个正整数 N，表示图中节点的数量。

第二行 N 个非负整数，其中第 i 个整数表示节点 i 的出边指向的节点序号(且不等于 i)，若为 0 则表示该节点为叶节点。

接下来一行一个正整数 Q，表示询问数目。

接下来 Q 行，每行包含一个上述格式的询问。 

输出格式:

对于每个类型 1 的询问，按照输入顺序，每行输出弹珠停止的节点序号。如果弹珠卡在某个地方永不停止，则输出 -1。

数据范围:

对于100%的数据：1 ≤ N , Q ≤ 3×105。

测试点编号 N Q 特殊性质
1 N ≤ 20 Q ≤ 20 无
2 N ≤ 100 Q ≤ 100 性质1
3 N ≤ 100 Q ≤ 100 性质2
4 N ≤ 100 Q ≤ 100 性质3
5 N ≤ 103 Q ≤ 103 无
6~7 N ≤ 104 Q ≤ 104 无
8~10 N ≤ 3×105 Q ≤ 3×105 无

【特殊性质】请参见下方的提示。

样例输入:

样例1：
3
2 3 1
7
1 1
1 2
2 1
1 2
1 1
2 2
1 2

样例2：
5
0 3 5 3 4
6
1 1
1 2
2 4
1 2
2 3
1 2

样例输出:

样例1：
-1
-1
1
1
2

样例2：
1
-1
4
3

提示:

【特殊性质】

其中本题有一些特殊性质：

特殊性质 ：保证最初图的形态是一条链。

特殊性质 ：保证最初图的形态是一个环。

特殊性质 ：保证最初图的形态是多个环。

时间限制: 1000ms
空间限制: 256MB

来源: 温州市计算机学会2023比赛