New Barns#10415

New Barns

1 second

128 megabytes

Very hard

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

Whenever FJ builds a new barn, he connects it with at most one bidirectional pathway to an existing barn. To make sure his cows are spread sufficiently far apart, he sometimes wants to determine the distance from a given barn to the farthest barn reachable from it (the distance between two barns is the number of pathways one must traverse to get from one barn to the other).

FJ will make a total of $q$ queries, each of which is either a build query or a distance query. In a build query, FJ builds a barn and connects it to at most one previously built barn. In a distance query, FJ asks for the distance from a given barn to the farthest barn reachable from it via a sequence of pathways. It is guaranteed that the queried barn has already been built. Help FJ answer all of these queries.

Input

The first line contains an integer $q (1 \leq q \leq 1 0^{5})$ q~(1 \le q \le 10^5) — the number of queries. Each of the next $q$ lines contains one query of the form B p or Q k. The query B p means that a new barn is built and connected to barn $p$ ; if $p = - 1$ p = -1, the new barn is not connected to any other barn, otherwise $p$ is the index of an already built barn. The query Q k asks for the distance from barn $k$ to the farthest barn reachable from it. Barns are numbered starting from $1$ in the order they are built: the first barn built is barn $1$ , the second is barn $2$ , and so on.

Output

For each distance query, print the answer on a separate line. Note that for a barn that is not connected to any other barn, the answer is $0$ .

Examples

The sample input corresponds to the following network of barns:

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

In query $1$ , we build barn $1$ . In query $2$ , we ask for the distance from barn $1$ to the farthest reachable barn. Since barn $1$ is not connected to any other barn, the answer is $0$ . In query $3$ , we build barn $2$ and connect it to barn $1$ . In query $4$ , we build barn $3$ and connect it to barn $2$ . In query $5$ , we ask for the distance from barn $3$ to the farthest reachable barn. In this case, the farthest one is barn $1$ , which is $2$ units away. In query $6$ , we build barn $4$ and connect it to barn $2$ . In query $7$ , we ask for the distance from barn $2$ to the farthest reachable barn. All three barns $1$ , $3$ and $4$ are at distance $1$ from it, so the answer is $1$ .

Example 1