SP22561 RTREE3 - Roger and tree III

上次遇到树的问题时，Roger 能够顺利解决，完全是因为有你的帮助。现在，他对树的学习更加深入和广泛（他特别喜欢解决连通无向无环图的问题）。然而，这次问题更加复杂，他已经花了一周的时间寻找解决方案，但仍未取得有效进展。不过，幸好有你这样的朋友，他相信只有你的编程技能能助他一臂之力。 问题是这样的：你会得到一个不断增长的树。最初，这棵树只有一个顶点 **1**。树会逐步增加：之后，顶点 **u** 会连接到 **1**，接着顶点 **v** 会连接到 **1** 或 **u**，如此继续，直到树包含 **N** 个顶点。在这个过程中，每当增加一个顶点时，你会被要求给出当前树中某个顶点 **x** 的偏心率。 在图 **G** 中，设 **x** 为其中一个顶点。 顶点 **x** 的偏心率定义为 **x** 到图 **G** 中任意其他顶点的最大距离。 即：**e (x) = max {d (x, y) : y 在 G 中}**。 当然，顶点 **y** 必须是已存在于当前树中的顶点。 此外，你还需要输出对应的顶点 **y**。 请你帮帮 Roger。

第一行包含两个整数 **N** 和 **M**，分别表示树的节点数和查询次数。 接下来的 M 行输入可能为两种类型："U x y" 或 "Q x"。 对于类型为 "U x y" 的输入，你需要将新顶点 **y** 连接到已有顶点 **x**。注意，**x** 已经在树中，而 **y** 则是新加入的节点。显然，这种输入共有 **(N - 1)** 次。

对于每个 "Q x" 类型的输入，你需要输出顶点 **x** 的偏心率，后面接着顶点 **y**。 如果有多个满足条件的顶点 **y**，输出编号最小的那个。

1 ≤ N, M ≤ 100,000 **本翻译由 AI 自动生成**