Minimum Reachable City

• 时间限制：3 秒
• 内存限制：512 MiB

题目描述

有一张 $N$ 个顶点的有向图 $G_S$，顶点编号为 $1$ 到 $N$。图中有 $N-1$ 条边：第 $i$ 条边（$1\le i\le N-1$）从顶点 $p_i$ 指向顶点 $i+1$，其中 $1\le p_i\le i$。因此 $G_S$ 是一棵以 $1$ 为根、边从父亲指向儿子的有根树。

另有一张初始与 $G_S$ 相同的有向图 $G$。请依次处理 $Q$ 个操作：

• 1 u v：向 $G$ 加入一条从 $u$ 指向 $v$ 的边。保证 $u\ne v$，且在原图 $G_S$ 中可以从 $v$ 沿若干条边到达 $u$。
• 2 x：输出在当前图 $G$ 中从 $x$ 沿若干条边能够到达的所有顶点（包括 $x$ 本身）中，编号最小的顶点编号。

输入格式

第一行一个整数 $N$。

第二行 $N-1$ 个整数 $p_1,p_2,\ldots,p_{N-1}$。

第三行一个整数 $Q$。

接下来 $Q$ 行，每行是上述两种操作之一。

输出格式

对每个 2 x 操作输出一行答案。

样例输入 1

5
1 2 3 3
5
2 4
1 4 2
2 4
1 5 1
2 4

样例输出 1

4
2
1

样例输入 2

7
1 1 2 2 3 3
10
2 5
1 5 2
2 5
1 2 1
1 7 1
1 6 3
2 5
2 6
2 1
1 7 1

样例输出 2

5
2
1
1
1

数据范围

对于所有数据：

• $2\le N\le 2\times10^5$；
• $1\le Q\le 2\times10^5$；
• $1\le p_i\le i$；
• 对操作 1 u v，$1\le u,v\le N$、$u\ne v$，且 $v$ 是 $u$ 在原树 $G_S$ 上的祖先；
• 对操作 2 x，$1\le x\le N$；
• 所有输入均为整数。

说明

样例 1 的第一次询问中，从 $4$ 只能到达 $4$；加入 $4\to2$ 后，从 $4$ 可到达 $2,3,4,5$；再加入 $5\to1$ 后，从 $4$ 可到达全部顶点。