题目描述

我们有一个有向图 $G$，它有 $N$ 个顶点，编号为 1 到 N。

它有 $N-1$ 条边。 第 $i$ 条边 ($1\leq i\leq N-1$) 从顶点 $p_i$ 出发($1\leq p_i\leq i$) 到顶点 $i+1$。

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

• 1 u v：向 $G$ 添加一条从顶点 $u$ 到顶点 $v$ 的边($1\leq u,v\leq N$)。保证满足以下条件:

1. $u\ne v.$

2. 在 $G$ 上，顶点 $u$ 也可以通过一些边从顶点 $v$ 到达。

• 2 x：输出从顶点 $x\ (1\leq x\leq N)$ 通过 $G$ 上的一些边(包括顶点 $x$)可达的顶点的最小顶点号。

数据范围

• $2\leq N\leq 2\times 10^5$

• $1\leq Q\leq 2\times 10^5$