题目描述

给你一棵树，初始没有节点。你需要支持两种操作：

• B p 表示新建一个节点，将它与 $p$ 节点连接；若 $p=-1$，则表示不与其它节点相连

• Q k 表示查询在 $k$ 节点所在的连通块中，距它最远的点的距离。这里距离的定义是两点间经过的边数。

输入格式

第一行一个正整数 $q$，表示操作个数。
接下来 $q$ 行，每行表示一个操作。

输出格式

对于每个询问操作，输出一行一个整数表示答案。

7
B -1
Q 1
B 1
B 2
Q 3
B 2
Q 2

0
2
1

提示

【数据范围】

对于 $100\%$ 的数据，$1 \le q \le 10^5$。
保证操作合法。

样例输入对应这棵树：

  (1) 
    \   
     (2)---(4)
    /
  (3)

在询问 $1$ 中，我们新建点 $1$。

在询问 $2$ 中，我们查询距点 $1$ 最远的点的距离。因为点 $1$ 不与其它任意点连通，答案为 $0$。

在询问 $3$ 中，我们新建点 $2$，并将其连接到点 $1$。

在询问 $4$ 中，我们新建点 $3$，并将其连接到点 $2$。

在询问 $5$ 中，我们查询距点 $3$ 最远的点的距离。在这里，答案是点 $1$，距其 $2$ 单位。

在询问 $6$ 中，我们新建点 $4$，并将其连接到点 $2$。

在询问 $7$ 中，我们查询距点 $2$ 最远的点的距离。点 $1, 3, 4$ 与其距离相等，均为 $1$。

命题人：Anson Hu