弹珠游戏

题目描述

兔警官朱迪解救了所有被困的动物之后，闲暇之余开始研究儿时的弹珠游戏，并邀请老朋友狐狸尼克一起玩。朱迪构造了一个包含 $N$ 个结点的有向图，其中每个结点的出度都不超过 $1$。随后，她会把一个弹珠放在某个结点上。只要弹珠当前位于结点 $X$，并且 $X$ 存在出边，弹珠就会沿着这条出边移动到相邻结点；若当前结点没有出边，则弹珠停止。也有可能由于图中存在环，使得弹珠永远不会停下。

朱迪会按顺序提出若干次询问，询问分为两类：

• 1 X：假设将弹珠放在结点 $X$ 上，询问弹珠最终停在哪个结点；如果弹珠会无限循环，则输出 $-1$。
• 2 X：删除结点 $X$ 的出边。题目保证在执行这条操作时，结点 $X$ 的出边一定存在。

特别地，所有询问都需要按输入顺序依次执行。也就是说，后续询问是在前面删除操作已经生效的基础上进行的。

输入格式

从标准输入按以下格式读取数据：

$N$

$a_1$ $a_2$ $\dots$ $a_N$

$Q$

接下来 $Q$ 行，每行一个询问

其中：

• 第一行输入一个正整数 $N$，表示图中结点的数量。
• 第二行输入 $N$ 个非负整数，其中第 $i$ 个整数 $a_i$ 表示结点 $i$ 的出边所指向的结点编号；如果 $a_i=0$，则表示结点 $i$ 没有出边；并且若 $a_i \ne 0$，则保证 $a_i \ne i$。
• 接下来一行输入一个正整数 $Q$，表示询问数目。
• 再接下来 $Q$ 行，每行包含一个上述格式的询问。

输出格式

对于每个类型为 1 X 的询问，按照输入顺序输出一行一个整数：

• 如果弹珠最终会停在某个结点，则输出该结点编号；
• 如果弹珠会在图中无限循环下去，则输出 -1。

数据范围

• $1 \le N,Q \le 3 \times 10^5$

部分测试点具有如下特殊性质：

• 性质 1：保证初始图的形态是一条链
• 性质 2：保证初始图的形态是一个环
• 性质 3：保证初始图的形态是多个环

样例

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

-1
-1
1
1
2

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

1
-1
4
3