새 건물

세리는 사람들이 너무 밀접하게 모이면 싸우게 된다는 것을 알아챘습니다. 그래서 그녀는 사람들을 퍼뜨리기 위해 새로운 건물을 여러개 짓기로 결심했습니다.

세리가 새 건물을 지을 때마다, 그는 최대 하나의 기존 건물과 양 방향 경로를 연결합니다. 사람들이 충분히 퍼져 있도록 하기 위해 그녀는 특정 건물에서 가장 멀리 떨어진 건물까지의 거리를 알고 싶어합니다 (두 건물 사이의 거리는 한 건물에서 다른 건물로 이동하기 위해 거쳐야 하는 경로의 수입니다).

세리는 총 $Q$ ($1 \leq Q \leq 10^5$)개의 질문을 할 것입니다. 각각은 "build" 또는 "distance" 형식 중 하나입니다. "build" 질문의 경우, 세리는 건물을 짓고 기존 건물 중 하나와 최대 하나의 경로를 연결합니다. "distance" 질문의 경우, 세리는 특정 건물에서 경로를 통해 도달할 수 있는 가장 먼 건물까지의 거리를 묻습니다. 질문이 들어온 건물은 이미 지어졌다는 것이 보장됩니다. 세리가 이러한 모든 질문에 대한 답변을 말하는 것을 도와주세요.

첫 번째 줄에 정수 $Q$가 주어집니다. 다음 $Q$개의 줄 각각에는 질문이 포함됩니다. 각 질문은 "B p" 또는 "Q k" 형식 중 하나입니다. "B p" 질문은 건물을 건설하고 건물 $p$와 연결하도록 지시하며, "Q k" 질문은 건물 $k$로부터 정의된 대로 가장 먼 거리를 제공합니다. 만약 $p = -1$이면, 새 건물은 다른 건물과 연결되지 않습니다. 그렇지 않으면 $p$는 이미 지어진 건물의 인덱스입니다. 건물 인덱스는 $1$부터 시작하므로 첫 번째 지어진 건물은 건물 $1$이 되며, 두 번째는 건물 $2$가 되고, 이와 같이 이어집니다.

각 거리 질문에 대해 한 줄의 출력을 작성하세요. 참고로, 다른 건물과 연결되지 않은 건물의 최대 거리는 $0$입니다.