CF1083C.Max Mex

Once Grisha found a tree (connected graph without cycles) with a root in node $1$.

But this tree was not just a tree. A permutation $p$ of integers from $0$ to $n - 1$ is written in nodes, a number $p_i$ is written in node $i$.

As Grisha likes to invent some strange and interesting problems for himself, but not always can solve them, you need to help him deal with two types of queries on this tree.

Let's define a function $MEX(S)$, where $S$ is a set of non-negative integers, as a smallest non-negative integer that is not included in this set.

Let $l$ be a simple path in this tree. So let's define indices of nodes which lie on $l$ as $u_1$, $u_2$, $\ldots$, $u_k$.

Define $V(l)$ as a set {$p_{u_1}$, $p_{u_2}$, $\ldots$ , $p_{u_k}$}.

Then queries are:

1. For two nodes $i$ and $j$, swap $p_i$ and $p_j$.
2. Find the maximum value of $MEX(V(l))$ in all possible $l$.

格里沙曾发现一棵以节点 $1$ 为根的树（即无环连通图）。

但这棵树并不仅仅是一棵普通的树：每个节点上写有一个 $0$ 到 $n-1$ 的排列 $p$，其中节点 $i$ 上写的数为 $p_i$。

由于格里沙喜欢为自己构思一些奇怪而有趣的问题，却并不总能自行解决，因此你需要帮助他处理该树上的两类查询。

我们定义函数 $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))$ 的最大值。

The first line contains a single integer $n$ ($2 \leq n \leq 2 \cdot 10^5$) — the number of nodes of a tree.

The second line contains $n$ integers — $p_1$, $p_2$, $\ldots$, $p_n$ ($0\leq p_i \lt n$) — the permutation $p$, it's guaranteed that all numbers are different .

The third line contains $n - 1$ integers — $d_2$, $d_3$, $\ldots$, $d_n$ ($1 \leq d_i \lt i$), where $d_i$ is a direct ancestor of node $i$ in a tree.

The fourth line contains a single integer $q$ ($1 \leq q \leq 2 \cdot 10^5$) — the number of queries.

The following $q$ lines contain the description of queries:

At the beginning of each of next $q$ lines, there is a single integer $t$ ($1$ or $2$) — the type of a query:

1. If $t = 1$, the line also contains two integers $i$ and $j$ ($1 \leq i, j \leq n$) — the indices of nodes, where values of the permutation should be swapped.
2. If $t = 2$, you need to find the maximum value of $MEX(V(l))$ in all possible $l$.

第一行包含一个整数 $n$（$2 \leq n \leq 2 \cdot 10^5$）——树的节点数量。

第二行包含 $n$ 个整数：$p_1$, $p_2$, $\ldots$, $p_n$（$0\leq p_i \lt n$）——排列 $p$，保证所有数值互不相同。

第三行包含 $n - 1$ 个整数：$d_2$, $d_3$, $\ldots$, $d_n$（$1 \leq d_i \lt i$），其中 $d_i$ 表示节点 $i$ 在树中的直接祖先。

第四行包含一个整数 $q$（$1 \leq q \leq 2 \cdot 10^5$）——查询的数量。

接下来的 $q$ 行描述了各次查询：

在接下来的每行开头，有一个整数 $t$（$1$ 或 $2$）——查询类型：

1. 若 $t = 1$，该行还包含两个整数 $i$ 和 $j$（$1 \leq i, j \leq n$）——需交换排列中对应节点 $i$ 和 $j$ 处的值。
2. 若 $t = 2$，你需要求出所有可能的 $l$ 中 $MEX(V(l))$ 的最大值。

For each type 2 query print a single integer — the answer for this query.

对于每个类型 2 的查询，输出一个整数——该查询的答案。

Number written in brackets is a permutation value of a node.

In the first example, for the first query, optimal path is a path from node $1$ to node $5$. For it, set of values is ${0, 1, 2}$ and $MEX$ is $3$.

For the third query, optimal path is a path from node $5$ to node $6$. For it, set of values is ${0, 1, 4}$ and $MEX$ is $2$.

In the second example, for the first query, optimal path is a path from node $2$ to node $6$. For it, set of values is ${0, 1, 2, 5}$ and $MEX$ is $3$.

For the third query, optimal path is a path from node $5$ to node $6$. For it, set of values is ${0, 1, 3}$ and $MEX$ is $2$.

For the fifth query, optimal path is a path from node $5$ to node $2$. For it, set of values is ${0, 1, 2, 3}$ and $MEX$ is $4$.

For the seventh query, optimal path is a path from node $5$ to node $4$. For it, set of values is ${0, 1, 2, 3}$ and $MEX$ is $4$.

For the ninth query, optimal path is a path from node $6$ to node $5$. For it, set of values is ${0, 1, 3}$ and $MEX$ is $2$.

括号中写的数字是节点的排列值。

在第一个样例中，对于第一次查询，最优路径是从节点 $1$ 到节点 $5$ 的路径。该路径上节点值的集合为 $\{0, 1, 2\}$，其 $MEX$ 值为 $3$。

对于第三次查询，最优路径是从节点 $5$ 到节点 $6$ 的路径。该路径上节点值的集合为 $\{0, 1, 4\}$，其 $MEX$ 值为 $2$。

在第二个样例中，对于第一次查询，最优路径是从节点 $2$ 到节点 $6$ 的路径。该路径上节点值的集合为 $\{0, 1, 2, 5\}$，其 $MEX$ 值为 $3$。

对于第三次查询，最优路径是从节点 $5$ 到节点 $6$ 的路径。该路径上节点值的集合为 $\{0, 1, 3\}$，其 $MEX$ 值为 $2$。

对于第五次查询，最优路径是从节点 $5$ 到节点 $2$ 的路径。该路径上节点值的集合为 $\{0, 1, 2, 3\}$，其 $MEX$ 值为 $4$。

对于第七次查询，最优路径是从节点 $5$ 到节点 $4$ 的路径。该路径上节点值的集合为 $\{0, 1, 2, 3\}$，其 $MEX$ 值为 $4$。

对于第九次查询，最优路径是从节点 $6$ 到节点 $5$ 的路径。该路径上节点值的集合为 $\{0, 1, 3\}$，其 $MEX$ 值为 $2$。