새 축사

존 농부는 소가 너무 가까이 모여 있으면 서로 다툰다는 것을 알아차렸다. 그래서 소를 넓게 흩어 놓으려고 축사를 하나씩 새로 짓기로 했다.

존은 축사를 새로 지을 때마다 이미 지어 둔 축사 중 많아야 한 곳과 양방향 통로로 잇는다. 소가 충분히 떨어져 있는지 확인하려고, 존은 어떤 축사에서 통로를 따라 갈 수 있는 가장 먼 축사까지의 거리를 알고 싶어 한다. 두 축사 사이의 거리는 한쪽에서 다른 쪽으로 갈 때 지나는 통로의 개수다.

존이 주는 질의는 모두 $Q$개($1 \leq Q \leq 10^5$)이며, 축사를 짓는 질의이거나 거리를 묻는 질의다. 짓는 질의에서 존은 축사를 하나 지어 이미 지어 둔 축사 중 많아야 한 곳과 잇는다. 거리 질의에서 존은 특정 축사에서 통로를 따라 갈 수 있는 가장 먼 축사까지의 거리를 묻는다. 질의에 나오는 축사는 이미 지어져 있다. 모든 질의에 답하라.

첫 줄에 정수 $Q$가 주어진다. 다음 $Q$개 줄에 질의가 한 줄에 하나씩 주어진다. 질의는 "B p" 또는 "Q k" 형태다. "B p"는 축사를 새로 지어 축사 $p$와 이으라는 뜻이고, "Q k"는 축사 $k$에서 가장 먼 축사까지의 거리를 답하라는 뜻이다. $p = -1$이면 새 축사는 어느 축사와도 잇지 않는다. 그렇지 않으면 $p$는 이미 지어 둔 축사의 번호다. 축사 번호는 $1$부터 시작한다. 가장 먼저 지은 축사가 $1$번, 그다음에 지은 축사가 $2$번이며, 이후에도 같은 방식으로 번호가 붙는다.

거리 질의마다 답을 한 줄에 하나씩 출력한다. 어느 축사와도 이어져 있지 않은 축사의 가장 먼 거리는 $0$이다.

예제 1의 입력은 아래와 같이 이어진 축사를 나타낸다.

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

질의 1에서 $1$번 축사를 짓는다. 질의 2에서는 $1$번에서 가장 먼 축사까지의 거리를 묻는다. $1$번은 어느 축사와도 이어져 있지 않으므로 답은 $0$이다. 질의 3에서 $2$번 축사를 지어 $1$번과 잇고, 질의 4에서 $3$번 축사를 지어 $2$번과 잇는다. 질의 5에서는 $3$번에서 가장 먼 축사를 묻는다. 가장 먼 축사는 $1$번이고 거리가 $2$이므로 답은 $2$다. 질의 6에서 $4$번 축사를 지어 $2$번과 잇는다. 질의 7에서는 $2$번에서 가장 먼 축사를 묻는다. $1$번, $3$번, $4$번이 모두 거리 $1$로 같으므로 답은 $1$이다.