最小可达顶点

题目描述

我们有一个包含 $N$ 个顶点的有向图 $G_S$，顶点编号为 $1$ 到 $N$。它有 $N-1$ 条边，第 $i$ 条边（$1\leq i \leq N-1$）从顶点 $p_i\ (1\leq p_i \leq i)$ 指向顶点 $i+1$。

我们还有另一个包含 $N$ 个顶点的有向图 $G$，顶点编号为 $1$ 到 $N$。初始时，$G$ 与 $G_S$ 相同。

请按给出的顺序处理 $G$ 上的 $Q$ 个查询。查询有以下两种。

• 1 u v：在 $G$ 中添加一条从顶点 $u$ 到顶点 $v$ 的边。 保证满足以下条件。
  • $u \neq v$。
  • 在 $G_S$ 上，从顶点 $v$ 可以经过若干条边到达顶点 $u$。
• 2 x：输出在 $G$ 上从顶点 $x$ 出发经过若干条边可以到达的顶点中，编号最小的顶点（包括顶点 $x$ 本身）。

输入格式

输入按以下格式从标准输入给出：

$N$
$p_1$ $p_2$ $\dots$ $p_{N-1}$
$Q$
$\mathrm{query}_1$
$\mathrm{query}_2$
$\vdots$
$\mathrm{query}_Q$

其中 $\mathrm{query}_i$ 表示第 $i$ 个查询，格式为以下两种之一：

$1$ $u$ $v$

$2$ $x$

输出格式

设第二种查询的个数为 $q$，输出 $q$ 行。 第 $j$ 行（$1\leq j \leq q$）输出第 $j$ 个第二种查询的答案。

样例

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

4
2
1

在第一个查询时，在 $G$ 上从顶点 $4$ 出发经过若干条边可以到达的顶点只有顶点 $4$ 本身。

在第三个查询时，在 $G$ 上从顶点 $4$ 出发可以到达顶点 $2,3,4,5$。

在第五个查询时，在 $G$ 上从顶点 $4$ 出发可以到达顶点 $1,2,3,4,5$。

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

5
2
1
1
1

数据范围

• $2\leq N \leq 2\times 10^5$
• $1\leq Q \leq 2\times 10^5$
• $1\leq p_i\leq i$
• 对于第一种格式的每个查询：
  • $1\leq u,v \leq N$。
  • $u \neq v$。
  • 在 $G_S$ 上，从顶点 $v$ 可以经过若干条边到达顶点 $u$。
• 对于第二种格式的每个查询，$1\leq x \leq N$。
• 输入中的所有值均为整数。