Description

You need to maintain a forest that initially has no nodes. Support two types of operations:

• B p builds a new node and connects it to node $p$. If $p = -1$, it is not connected to any other node.
• Q k asks, within the connected component containing node $k$, for the distance to the farthest node from it. The distance is defined as the number of edges on the path between two nodes.

Input Format

The first line contains a positive integer $q$, the number of operations.
The next $q$ lines each describe one operation.

Output Format

For each query operation, output one integer per line representing the answer.

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

0
2
1

Hint

Constraints: For $100\%$ of the testdata, $1 \le q \le 10^5$. The operations are guaranteed to be valid.

The example input corresponds to this network of barns:

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

In query 1, we build barn number 1. In query 2, we ask for the distance of 1 to the farthest connected barn. Since barn 1 is connected to no other barns, the answer is 0. In query 3, we build barn number 2 and connect it to barn 1. In query 4, we build barn number 3 and connect it to barn 2. In query 5, we ask for the distance of 3 to the farthest connected barn. In this case, the farthest is barn 1, which is 2 units away. In query 6, we build barn number 4 and connect it to barn 2. In query 7, we ask for the distance of 2 to the farthest connected barn. All three barns 1, 3, 4 are the same distance away, which is 1, so this is our answer.

Problem credits: Anson Hu.

Translated by ChatGPT 5