题目描述

题目来自 USACO 2018 February Contest, Platinum Problem 2. New Barns

Farmer John 注意到他的奶牛们如果被关得太近就容易吵架，所以他想开放一些新的牛棚来分散她们。

每当 FJ 建造一个新牛棚的时候，他会将这个牛棚用至多一条双向道路与一个现有的牛棚连接起来。为了确保他的奶牛们足够分散，他有时想要确定从某个特定的牛棚出发，到它能够到达的最远的牛棚的距离（两个牛棚之间的距离等于从一个牛棚出发到另一个之间必须经过的道路条数）。

FJ 总共会给出 $Q$（$1\le Q\le 10^5$）次请求，每个请求都是「建造」和「距离」之一。对于一个建造请求，FJ 建造一个牛棚，并将其与至多一个现有的牛棚连接起来。对于一个距离请求，FJ 向你询问从某个特定的牛棚通过一些道路到离它最远的牛棚的距离。保证询问的牛棚已经被建造。请帮助 FJ 响应所有的请求。

输入格式

第一行包含一个整数 $Q$。

以下 $Q$ 行，每行包含一个请求。每个请求的格式都是「B p」或是「Q k」，分别告诉你建造一个牛棚并与牛棚 $p$ 连接，或是根据定义求从牛棚 $k$ 出发最远的距离。如果 $p=-1$，则新的牛棚不会与其他牛棚连接。否则，$p$ 是一个已经建造的牛棚的编号。牛棚编号从 $1$ 开始，所以第一个被建造的牛棚是 $1$ 号牛棚，第二个是 $2$ 号牛棚，以此类推。

输出格式

对于每个距离请求输出一行。注意一个没有连接到其他牛棚的牛棚的最远距离为 $0$。

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

0
2
1

输入样例对应下面的牛棚网：

  (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$ 都与 $2$ 相距相同的距离 $1$，所以这就是我们的回答。