New Barns

Farmer John notices that his cows tend to get into arguments if they are packed too closely together, so he wants to open a series of new barns to spread them out.

Whenever John builds a new barn, he connects it with at most one bidirectional pathway to a barn that already exists. To make sure his cows are spread far enough apart, he sometimes wants the distance from a certain barn to the farthest barn reachable from it. The distance between two barns is the number of pathways you traverse to go from one to the other.

John gives $Q$ ($1 \leq Q \leq 10^5$) queries in total, each either a build query or a distance query. In a build query, John builds one barn and links it with at most one previously built barn. In a distance query, John asks for the distance from a certain barn to the farthest barn reachable from it along the pathways. The queried barn has already been built. Answer all of the queries.

The first line contains the integer $Q$. Each of the next $Q$ lines contains one query, either "B p" or "Q k", telling you to build a barn and connect it with barn $p$, or to report the farthest distance from barn $k$. If $p = -1$, the new barn is connected to no other barn. Otherwise $p$ is the index of a barn that has already been built. Barn indices start from $1$, so the first barn built is barn $1$, the second is barn $2$, and the numbering continues that way.

Print one line for each distance query. A barn that is connected to no other barn has farthest distance $0$.

The input of the first example corresponds to this network of barns.

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

Query 1 builds barn $1$. Query 2 asks for the distance from barn $1$ to the farthest connected barn. Barn $1$ is connected to no other barn, so the answer is $0$. Query 3 builds barn $2$ and connects it to barn $1$, and query 4 builds barn $3$ and connects it to barn $2$. Query 5 asks for the farthest barn from barn $3$. The farthest one is barn $1$ at distance $2$, so the answer is $2$. Query 6 builds barn $4$ and connects it to barn $2$. Query 7 asks for the farthest barn from barn $2$. Barns $1$, $3$ and $4$ all sit at distance $1$, so the answer is $1$.