Bác nông dân John nhận thấy đàn bò của mình có xu hướng tranh cãi nếu chúng bị nhốt quá gần nhau, vì vậy ông muốn mở một loạt chuồng bò mới để giúp chúng giãn ra.

Mỗi khi xây một chuồng bò mới, bác nông dân John nối nó với nhiều nhất một chuồng đã có bằng một lối đi hai chiều. Để bảo đảm đàn bò được phân tán đủ xa nhau, đôi khi ông muốn xác định khoảng cách từ một chuồng nhất định đến chuồng xa nhất có thể đi tới từ đó (khoảng cách giữa hai chuồng là số lối đi phải đi qua để từ chuồng này đến chuồng kia).

Bác nông dân John sẽ đưa ra tổng cộng \(Q\) truy vấn (\(1 \leq Q \leq 10^5\)), mỗi truy vấn thuộc loại “xây” hoặc “khoảng cách”. Với truy vấn xây, bác nông dân John xây một chuồng và nối nó với nhiều nhất một chuồng đã được xây trước đó. Với truy vấn khoảng cách, ông hỏi khoảng cách từ một chuồng nhất định đến chuồng xa nhất có thể đi tới từ đó qua một chuỗi các lối đi. Bảo đảm rằng chuồng được truy vấn đã được xây. Hãy giúp bác nông dân John trả lời tất cả các truy vấn này.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên \(Q\). Mỗi dòng trong \(Q\) dòng tiếp theo chứa một truy vấn. Mỗi truy vấn có dạng B p hoặc Q k, lần lượt yêu cầu xây một chuồng và nối nó với chuồng \(p\), hoặc cho biết khoảng cách xa nhất như đã định nghĩa từ chuồng \(k\). Nếu \(p = -1\) thì chuồng mới sẽ không được nối với chuồng nào khác. Nếu không, \(p\) là chỉ số của một chuồng đã được xây. Chỉ số các chuồng bắt đầu từ \(1\), nên chuồng được xây đầu tiên là chuồng \(1\), chuồng thứ hai là chuồng \(2\), và cứ tiếp tục như vậy.

Dữ liệu ra

In ra một dòng cho mỗi truy vấn khoảng cách. Lưu ý rằng một chuồng không nối với bất kỳ chuồng nào khác có khoảng cách xa nhất bằng \(0\).

Ví dụ

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

0
2
1

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

Nguồn

USACO 2018 February Contest, Platinum — New Barns

Tác giả bài toán: Anson Hu.