一旦 Grisha 发现一棵树(无循环的连通图),其根位于节点 $$$1$$$ 中。
但这棵树不仅仅是一棵树。从 $$$0$$$ 到 $$$n - 1$$$ 的整数排列 $$$p$$$ 写入节点中,数字 $$$p_i$$$ 写入节点 $$$i$$$ 中。
由于 Grisha 喜欢为自己发明一些奇怪而有趣的问题,但并不总是能解决它们,你需要帮助他处理这棵树上的两种类型的查询。
让我们定义一个函数$$$MEX(S)$$$,其中$$$S$$$是一组非负整数,作为不包含在该集合中的最小非负整数。
让 $$$l$$$ 成为该树中的简单路径。因此,我们将 $$$l$$$ 上的节点索引定义为 $$$u_1$$$、$$$u_2$$$、$$$\ldots$$$、$$$u_k$$$。
将 $$$V(l)$$$ 定义为集合 {$$$p_{u_1}$$$, $$$p_{u_2}$$$, $$$\ldots$$$ , $$$p_{u_k}$$$}。
那么查询是:
1. 对于两个节点 $$$i$$$ 和 $$$j$$$,交换 $$$p_i$$$ 和 $$$p_j$$$。
2. 找出所有可能的$$$l$$$中$$$MEX(V(l))$$$的最大值。
输入
第一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$) — 树的节点数。
第二行包含 $$$n$$$ 整数 — $$$p_1$$$, $$$p_2$$$, $$$\ldots$$$, $$$p_n$$$ ($$$0\leq p_i < n$$$) — 排列 $$$p$$$,保证所有数字都不同。
第三行包含 $$$n - 1$$$ 整数 — $$$d_2$$$、$$$d_3$$$、$$$\ldots$$$、$$$d_n$$$ ($$$1 \leq d_i < i$$$),其中 $$$d_i$$$ 是树中节点 $$$i$$$ 的直接祖先。
第四行包含一个整数 $$$q$$$ ($$$1 \leq q \leq 2 \cdot 10^5$$$) — 查询数。
以下 $$$q$$$ 行包含查询的描述:
在接下来的 $$$q$$$ 行的开头,有一个整数 $$$t$$$($$$1$$$ 或 $$$2$$$)——查询的类型:
1. 如果 $$$t = 1$$$,则该行还包含两个整数 $$$i$$$ 和 $$$j$$$ ($$$1 \leq i, j \leq n$$$) — 节点的索引,其中应交换排列值。
2. 如果$$$t = 2$$$,则需要在所有可能的$$$l$$$中找到$$$MEX(V(l))$$$的最大值。
输出
对于每个类型 2 查询,打印一个整数 - 该查询的答案。
示例
输入 #1
6 2 5 0 3 1 4 1 1 3 3 3 3 2 1 6 3 2
输出 #1
3 2
输入 #2
6 5 2 1 4 3 0 1 1 1 3 3 9 2 1 5 3 2 1 6 1 2 1 4 2 2 1 1 6 2
输出 #2
3 2 4 4 2
注意
括号内的数字是节点的排列值。