AT_tkppc2015_j.仕事をしよう！ (Working!)

joisino姐姐惊醒时发现自己坐在家里的电视机前，似乎之前一直在做梦。
但她意识到，从开始看电视到现在已经过去了很长时间，墙上的时钟显示离上班时间只剩一个小时。

幸运的是，joisino姐姐上班的市政府离家很近。
她悠然地到达了办公室，却突然被告知被调到了道路整备课。

这个城市目前正在进行大规模的城市开发，交通拥堵问题令人担忧。
因此，市政府让joisino姐姐负责监控交通状况。

现在，市里只有1个都市。
但随着城市开发的进行，预计会有更多的都市出现。
新建都市时，会选择一个现有都市，并与之通过一条道路相连。
所以，如果都市的数量是 $n$，就会有 $n-1$ 条道路。
最初的都市称为都市0，第 $i(1 \le i)$ 个创建的都市称为都市 $i$，第 $i(1 \le i)$ 条修建的道路称为道路 $i$。

每个都市的人口在变化，因此每条道路的通行时间也随之改变。
为了提高居民的便利性，还需要知道从某个都市出发到达最远的都市需要的时间。

在这种情况下，joisino姐姐将会收到 $Q$ 个关于都市的查询，
第 $i(1 \le i \le Q)$ 个查询可能是以下三种情况之一：

• 查询1：新建一个都市，与都市 $A_i$ 通过时间为 $C_i$ 的道路相连。
• 查询2：修改道路 $A_i$ 的通行时间为 $C_i$。
• 查询3：查询从都市 $A_i$ 出发到达最远的都市所需的时间。

对于查询3的情况，必须给出答案。

由于工作繁琐，joisino姐姐想编写一个程序来帮助她完成这些任务。

输入由以下格式通过标准输入给出：

第一行是一个整数 $Q (1 \le Q \le 5 \times 10^5)$，表示查询数量。

接下来的 $Q$ 行中，第 $i$ 行包含三个整数 $T_i (1 \le T_i \le 3), A_i (0 \le A_i \le 当前存在的都市数量 - 1), C_i$，以空格分隔。

• 当 $T_i = 1$ 时，表示新建一个都市，通过时间为 $C_i (1 \le C_i \le 10^9)$ 的道路与都市 $A_i$ 相连。
• 当 $T_i = 2$ 时，表示将道路 $A_i$ 的通行时间修改为 $C_i (1 \le C_i \le 10^9)$。
• 当 $T_i = 3$ 时，表示查询从都市 $A_i$ 出发到最远的都市所需的时间，忽略 $C_i$。如果只有一个都市，答案为0。

输出中每行对应一个查询3的答案。
在所有答案后面输出一个换行符。

分值划分

该问题有部分评分：

• 数据集1满足 $Q \le 10^4$，正确处理可得5分。
• 数据集2没有额外限制，正确处理可得155分。

示例解释1

下面是处理这些查询的过程：

• 查询1：新建都市1，与都市0通过时间为10的道路相连。
• 查询2：新建都市2，与都市1通过时间为7的道路相连。
• 查询3：查询从都市1出发到最远的都市，需要时间10（到达都市0）。
• 查询4：将道路2的通行时间修改为5。
• 查询5：新建都市3，与都市0通过时间为17的道路相连。
• 查询6：查询从都市0出发到最远的都市，需要时间17（到达都市3）。

处理完所有查询后的城市结构如下图所示：

示例解释2

0
15

在这个例子中，发生了以下事情：

• 查询1：从都市0出发，没有其他都市，输出0。
• 查询2：新建都市1，��都市0通过时间为10的道路相连。
• 查询3：将道路1的通行时间修改为15。
• 查询4：新建都市2，与都市0通过时间为7的道路相连。
• 查询5：新建都市3，与都市2通过时间为5的道路相连。
• 查询6：新建都市4，与都市2通过时间为8的道路相连。
• 查询7：查询从都市0出发到最远的都市，需要时间15（到达都市1或都市4）。

处理完所有查询后的城市结构如下图所示：

本翻译由 AI 自动生成